Вопросы с меткой [теория-чисел]

Теория чисел (в узком смысле) занимается свойствами целых чисел: делимостью (простые числа, НОД/НОК, сравнения по модулю), решением уравнений в целых числах (диофантовы уравнения, пифагоровы тройки). К ней же относятся цепные дроби, числа Фибоначчи (и многие другие числа с именами), большая и малая теоремы Ферма и многое, многое другое.

Фильтрация
Сортировка
Метки
0 голосов
1 ответ
125 показов

дано натуральное число, проверьте можно ли данное натуральное число вычислить произведением трех простых чисел

Есть задача, не могу придумать решение, даже мысли нет, точнее как, мысли есть, сделать решето эратосфена, все числа вносить в массив, но как тогда мне нужно это все правильно перемножить? На сколько ...
user23328595's user avatar
0 голосов
0 ответов
105 показов

Задача о подсчете делителей и сравнению их количества, не могу найти ошибку

Всем привет, решала такую задачу: ограничение по времени на тест: 1 секунда ограничение по памяти на тест: 256 мегабайт У каждого духа есть имя — натуральное число, и сила — количество делителей имени....
Настя's user avatar
1 голос
2 ответа
84 показа

Работа с праймориалами. Поиск n-ого члена праймориала

Нам дана разность двух праймориалов (это произведение простых чисел) p_a# и p_b#. Нужно найти а-ый и b-ый члены соответствующих праймориалов. Гарантируется, что X (разность праймориалов) меньше 10^18....
Markovit's user avatar
-3 голоса
1 ответ
43 показа

Задача на подсчет переодически последовательностей

Нужно посчитать количество бесконечных в обе стороны двоичных последовательностей (из 0 и 1), периодических с данным периодом(не обязательно главным), при чем если последовательности получаются друг ...
Igirlt's user avatar
  • 13
-4 голоса
1 ответ
179 показов

помогите решить задачу за короткое алгоритмическое время [закрыт]

1.5.4. Факториал по модулю Ограничение времени 1 секунда Ограничение памяти 64Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt Во входном файле задано целое ...
Ильяс Закиров's user avatar
1 голос
1 ответ
46 показов

Неопределённая ошибка в тесте на Кармайкловы числа

Никак ни могу понять где ошибка в коде, все вроде выходит из определения чисел Кармайкла, но тем не менее программа их не видит. k = int(input()) def is_prime(x): for j in range(2, x // 2 + 1): ...
Cacat's user avatar
  • 11
1 голос
3 ответа
280 показов

Число делителей факториала

я написала код по задаче: По заданному натуральному числу N необходимо вычислить количество натуральных чисел, которые есть делителями N! (факториала числа N). Например, при N=4, N!=4·3·2·1=24. Это ...
Настя's user avatar
2 голоса
1 ответ
67 показов

Подсчет суммы сочетаний

Нужно найти сумму сочетаний: на вход дается 3 числа: n, m, l (1<= n, m, l <= 10^6) пробовал через itertools, но использует слишком много памяти при больших тестах, math.comb не работает на ...
Мирон Климов's user avatar
7 голосов
3 ответа
348 показов

Программа для поиска приветливых чисел

Назовём натуральное число приветливым, если для любого натурального n⩾2 энная цифра этого числа равна остатку этого числа при делении на n . Например, число 2123 является приветливым, так как даёт ...
Ян Альбертович Дененберг's user avatar
0 голосов
1 ответ
531 показ

Алгоритм нахождения всех делителей большого числа

Мне попалась задача, суть такова: сложить делители числа n и сравнить сумму с самим n. Но вопрос не про это - вопрос в том, чтобы найти эти делители для огромных чисел, например, для 23_459_879_034. ...
Emil Gerz's user avatar
0 голосов
1 ответ
977 показов

Алгоритм перебора чисел

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, ...
Marilyn Manson's user avatar
1 голос
3 ответа
2k показов

Найдите пять наименьших значений k, при которых N(k) имеет нечётное количество различных чётных делителей

Пусть N(k) = 1 850 000 000 + k, где k – натуральное число. Найдите пять наименьших значений k, при которых N(k) имеет нечётное количество различных чётных делителей. В ответе запишите найденные ...
daniil's user avatar
  • 23
1 голос
1 ответ
136 показов

возможно ли из a получить b

всем привет, есть два числа, нужно проверить возможно ли получить из числа a другое число b, умножая его на число которое делится на a и посчитать кол-во шагов за которое это можно сделать, например: ...
ch1ba's user avatar
  • 63
1 голос
1 ответ
167 показов

Задача на gcd, не понятна логика условия

В начале игры у вас есть массив a длины n. За один ход можно выбрать два соседних элемента и заменить один из них на наибольший общий делитель этих двух чисел. То есть из двух соседних чисел x и y ...
Диана's user avatar
-1 голос
2 ответа
307 показов

Задача на автоморфные числа. Язык Си

Автоморфными называются числа, которые содержатся в последних разрядах их квадрата, например, десятичные числа: 52 = 25, 252 = 625. Автоморфные числа существуют в системе счисления, основание n ...
Myth Math's user avatar
0 голосов
2 ответа
132 показа

Алгоритм сам завершается(хотя должен продолжаться)

Условие: Алгоритм принадлежит числовому отрезку [A;B] (1<A<B<1000000) выводит числа,имеющие среди делителей ровно три различных натуральных нечетных делителя, не считая 1 и само число(если ...
Wismut's user avatar
  • 15
0 голосов
1 ответ
501 показ

C++ программа которая выводит на экран количество простых чисел среди введённых

Пользователь вводит в с клавиатуры десять чисел больше двух, нужно что бы программа выводила количество простых чисел среди введённых Понимаю что код не правильный, но нужна максимально простая ...
Nightwalker's user avatar
0 голосов
1 ответ
152 показа

Оптимизация алгоритма "Забавная игра"

Помогите, пожалуйста, оптимизировать алгоритм по времени выполнения. Признаюсь, переписал его с питона, потому что мой выполнялся ещё дольше. Мне кажется нужно концептуально поменять решение. Вот ...
Владимир Попов's user avatar
1 голос
2 ответа
404 показа

Слишком большие числа для long long

Есть функция factorial(n), которая находит n!: long long factorial(int n) { if (n == 0) return 1; return n * factorial(n - 1); } А также функция factorization(n), которая находит ...
Thwrani's user avatar
  • 159
2 голоса
2 ответа
683 показа

Задача "Суперчисла"

Имеется задача: Суперчислом называется число, являющееся суммой двух простых чисел из диапазона [2…B]. Требуется найти все суперчисла из заданного диапазона [A…B]. (2 <= A <= B <= 40000) ...
Thwrani's user avatar
  • 159
2 голоса
2 ответа
109 показов

Почему возникает Memory Limit Exceed?

В контесте нужно решить следующую задачу: На вершине лесенки, содержащей n ступенек, сидит кузнечик, который хочет спуститься вниз, к основанию. Кузнечик умеет прыгать на следующую ступеньку, на ...
demmen's user avatar
  • 304
1 голос
1 ответ
673 показа

Задача "Степень"

Дана задача: Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N ...
Thwrani's user avatar
  • 159
2 голоса
3 ответа
5k показов

Найти наибольший простой делитель одного целого числа БЕЗ ДЕЛЕНИЯ

Нужен простой наибольший делитель целого числа !НО по заданию нельзя использовать операции деления ( / и % ) Нужен алгоритм. не пойму от чего отталкиваться.
el Muerto de Mederti's user avatar
0 голосов
1 ответ
58 показов

Неверная работа кода при "длинных" входных данных

Всем привет. Задачка с CodeWars "Kids and candies". С условием можете ознакомиться по ссылке https://www.codewars.com/kata/56cca888a9d0f25985000036/python . Суть в том, что нужно найти НОК ...
Николай Бруцкий-Стемпковский's user avatar
0 голосов
0 ответов
494 показа

Найти обратный элемент в конечном поле

Интересует такой вопрос. У нас есть поле Галуа GF(2^8), в нем задается элемент в байтовом представлении (допустим, А = 1Е, то бишь 00011110 в двоичной системе счисления, а значит, если представлять ...
asavva's user avatar
  • 71
0 голосов
1 ответ
881 показ

Четные - нечетные (С++)

Программа получает на вход два целых положительных числа A и B, не превосходящие 2×10^9. Мне надо сделать оптимизацию, чтобы программа считывала разность четной и нечетной быстрее. Каким способом ...
reiwoo's user avatar
  • 23
-1 голос
1 ответ
331 показ

На какую максимальную степень K делится число N! через разложение на простые множители

В интернете увидел способ решения задачи, но никак не могу понять, как работает разложение на множители. Число k раскладываем на множители вида "число - степень", а после делим простые ...
Savvon's user avatar
  • 13
3 голоса
2 ответа
342 показа

Дружественные числа. Выход за временные рамки

Даны два целых положительных числа M, N. Требуется найти все «дружественные» пары чисел на отрезке [M; N]. Дружественным для числа А является такое число В, что оно равно сумме делителей А, исключая ...
Game_SHOW_LD's user avatar
2 голоса
3 ответа
357 показов

Наименьшее натуральное число, сумма делителей которого не меньше миллиона

Рассмотрим последовательность: 1, 6, 48, 360, 3120, 27720, ? Энный элемент этой последовательности равен наименьшему натуральному числу, имеющему эн-значную сумму делителей (включая 1 и само число). ...
Ян Альбертович Дененберг's user avatar
-2 голоса
2 ответа
105 показов

Как найти общие вершины двух правильных многоугольников? [закрыт]

Скажите, пожалуйста, как можно решить эту задачу. Что-то совсем не могу понять как это можно реализовать.. В окружность вписаны N-угольник и M-угольник. Известно, что многоугольники правильные и имеют ...
jassiiccaa2020's user avatar
2 голоса
4 ответа
1k показов

Посчитать количество красивых чисел

На просторах интернета нашел интересную задачу: Нужно посчитать кол-во красивых (сумма первых шести чисел равна сумме шести последних цифр) 13-значных чисел в 13-значной системе счисления, например: ...
QuickDzen's user avatar
  • 713
1 голос
1 ответ
161 показ

Подсчитать больше 8 автоморфных чисел

Задание: Автоморфными называются числа, которые содержатся в последних разрядах их квадрата, например, десятичные числа: 5^2 = 25, 25^2 = 625. Автоморфные числа существуют в системе счисления, ...
Екатерина Решетняк's user avatar
1 голос
2 ответа
926 показов

Найти сумму простых делителей числа N

При вводе любого значения ничего не выводится #include <stdio.h> #include <conio.h> int main() { int n, sum = 1; if (scanf("%lf", n) == 0) { printf("...
MicroHuman's user avatar
3 голоса
2 ответа
303 показа

Найти наименьшее екатериноекатерининское число

Натуральное число, превышающее 1, назовём екатериноекатерининским, если оно делится как на число своих делителей, так и на обоих его соседей по натуральному ряду. [то есть, если число это N, а число ...
Ян Альбертович Дененберг's user avatar
0 голосов
2 ответа
7k показов

Поиск дружественных пар чисел с помощью циклов

Составьте программу для решения задачи. Два натуральных числа называются дружественными, если каждое из них равно сумме всех делителей другого (само другое число в качестве делителя не рассматривается)...
Daniil Vlasov's user avatar
2 голоса
3 ответа
723 показа

НОД чисел Фибоначчи

Помогите, пожалуйста, понять в чём ошибка. Как известно, последовательность Фибоначчи определяется следующим образом: F(0) = 0, F(1) = 1, F(n) = F(n-1)+F(n-2) (для всех n > 1). По заданным n и m ...
nikita sokolov's user avatar
2 голоса
3 ответа
1k показов

Представление натурального числа в виде суммы квадратов натуральных чисел, слишком «‎медленный» код

# Представление натурального числа # в виде суммы квадратов # натуральных чисел. k=int(input()) for i in range(1, k+1): if k==i**2: print(i) for i in range(1, k+1): for j in range(i,...
Ян Альбертович Дененберг's user avatar
3 голоса
4 ответа
853 показа

Считаем пары если заданы НОД и НОК

Код не проходит по времени. Задано два натуральных числа A и B. Найти кол-во таких пар чисел (P, Q), для которых A является НОД(P, Q), а B - НОК(P, Q). Входные данные : В единственном ряде два ...
nikita sokolov's user avatar
1 голос
2 ответа
1k показов

Задача на магический квадрат с умножением 3x3 [закрыт]

Из собеседования на джуниора, нужно было быстро решить. Я не решил, гугл не помог. Гуглится якобы решенный квадрат, но при проверке произведения там разные. Возьмем числа от трех до одиннадцати и ...
John Nix's user avatar
1 голос
1 ответ
224 показа

Не понимаю в чем ошибка, требуется вывести ответ по модулю

Программа должна найти сумму всех сочетаний, где k от 1 до l. Я использовал все через модуль. И формулу на картинке ниже. Example_1: Input: 3 1 3 Output: 7 Example_2: Input: 3 4 3 Output: 0 ...
SionM's user avatar
  • 13
3 голоса
1 ответ
1k показов

Задача Обратные числа C++

Обратное число В этой задаче нужно ответить на 1≤t≤105 запросов. Каждый запрос состоит из двух целых чисел 2≤p≤109 и 0<a<p, число p является простым. На каждый запрос нужно вывести в отдельной ...
EgorWork's user avatar
  • 140
1 голос
2 ответа
3k показов

Нахождение трех четных делителя в промежутке

Найдите все натуральные числа, принадлежащие отрезку [101 000 000; 102 000 000], у которых ровно 3 различных чётных делителей (количество нечётных делителей может быть любым). В ответе перечислите ...
Alex's user avatar
  • 27
0 голосов
1 ответ
166 показов

Time limit exeeded

Задача на acmp.ru "Осколки" На Землю надвигается страшная угроза, к нам летит облако из N огромных астероидов. Известно только то, что все они одинакового размера. У учёных есть ракеты, ...
Roman's user avatar
  • 1
1 голос
1 ответ
182 показа

Делимость n! на n^2 C++

Как проверить делимость n! на n во второй степени ( n2 )?
Brin's user avatar
  • 31
1 голос
1 ответ
126 показов

Как высчитать степень?

я прочитал теорему как разложить простой число на множители и не понял нечего, да я знаю что здесь min, max это функции которые принимают со своих параметров наибольшие или наименьшее значения: пример ...
infinity's user avatar
3 голоса
2 ответа
324 показа

Оптимизация программы поиска количества нулей в конце факториала числа

import math num = int(input()) num = math.factorial(num) countZero = 0 while (num % 10 == 0): num //= 10 countZero += 1 print(countZero)
d4riy's user avatar
  • 67
3 голоса
1 ответ
2k показов

Докажите, что количество делителей квадрата натурального числа - число нечетное

Задача: Докажите, что количество делителей квадрата натурального числа - число нечетное. Сформулируйте и докажите обратное утверждение. Указание: Все делители числа n^2, кроме одного, можно разбить ...
Bohdan Pylypenko's user avatar
0 голосов
1 ответ
58 показов

Подскажите, пожалуйста, почему этот код иногда выводит 1 вместо нужного числа

Подскажите, пожалуйста, почему этот код иногда выводит 1 вместо нужного числа. Спасибо #include <stdlib.h> #include <stdio.h> int main(){ int isicc; ...
Foss's user avatar
  • 3
1 голос
1 ответ
2k показов

Требуется получить и вывести на экран количество всех возможных различных способов представления этого числа в виде суммы натуральных чисел

то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа Пример: Введите натуральное число: 4 Количество разложений: 4
ApTuMoLLIKa's user avatar
-1 голос
2 ответа
1k показов

Сумма цифр шестнадцатеричного числа [закрыт]

Найти однозначное число которое получается вычислением суммы цифр шестнадцатеричного числа(беззнаковое) n (повторно). Пример: 40820A2 -> 4 + 0 + 8 + 2 + 0 + A + 2 = 1A; 1A -> 1 + A = B Т.е. ...
TigerTV.ru's user avatar
  • 3,225