Как найти делители числа на отрезке

Сайт переезжает. Большинство статей уже перенесено на новую версию.
Скоро добавим автоматические переходы, но пока обновленную версию этой статьи можно найти там.

Теория чисел

• Простые числа
• Разложение на простые множители
• Решето Эратосфена
• Линейное решето Эратосфена*
• НОД и НОК
• Алгоритм Евклида
• Расширенный алгоритм Евклида*
• Операции по модулю
• Быстрое возведение в степень
• Деление по простому модулю*

Простые числа

Простым называется натуральное число, которое делится только на единицу и на себя. Единица при этом простым числом не считается. Составным числом называют непростое число, которое еще и не единица.

Примеры простых чисел: (2), (3), (5), (179), (10^9+7), (10^9+9).

Примеры составных чисел: (4), (15), (2^{30}).

Еще одно определение простого числа: (N) — простое, если у (N) ровно два делителя. Эти делители при этом равны (1) и (N).

Проверка на простоту за линию

С точки зрения программирования интересно научиться проверять, является ли число (N) простым. Это очень легко сделать за (O(N)) — нужно просто проверить, делится ли оно хотя бы на одно из чисел (2, 3, 4, ldots, N-1) . (N > 1) является простым только в случае, если оно не делится на на одно из этих чисел.

def is_prime(n):
    if n == 1:
        return False
    for i in range(2, n): # начинаем с 2, так как на 1 все делится; n не включается
        if n % i == 0:
            return False
    return True

for i in range(1, 10):
    print(i, is_prime(i))

(1, False)
(2, True)
(3, True)
(4, False)
(5, True)
(6, False)
(7, True)
(8, False)
(9, False)

Проверка на простоту за корень

Алгоритм можно ускорить с (O(N)) до (O(sqrt{N})).

Пусть (N = a times b), причем (a leq b). Тогда заметим, что (a leq sqrt N leq b).

Почему? Потому что если (a leq b < sqrt{N}), то (ab leq b^2 < N), но (ab = N). А если (sqrt{N} < a leq b), то (N < a^2 leq ab), но (ab = N).

Иными словами, если число (N) равно произведению двух других, то одно из них не больше корня из (N), а другое не меньше корня из (N).

Из этого следует, что если число (N) не делится ни на одно из чисел (2, 3, 4, ldots, lfloorsqrt{N}rfloor), то оно не делится и ни на одно из чисел (lceilsqrt{N}rceil + 1, ldots, N-2, N-1), так как если есть делитель больше корня (не равный (N)), то есть делитель и меньше корня (не равный 1). Поэтому в цикле for достаточно проверять числа не до (N), а до корня.

def is_prime(n):
    if n == 1:
        return False
    # Удобно вместо for i in range(2, n ** 0.5) писать так:
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

for i in [1, 2, 3, 10, 11, 12, 10**9+6, 10**9+7]:
    print(i, is_prime(i))

(1, False)
(2, True)
(3, True)
(10, False)
(11, True)
(12, False)
(1000000006, False)
(1000000007, True)

Разложение на простые множители

Любое натуральное число можно разложить на произведение простых, и с такой записью очень легко работать при решении задач. Разложение на простые множители еще называют факторизацией.

[11 = 11 = 11^1] [100 = 2 times 2 times 5 times 5 = 2^2 times 5^2] [126 = 2 times 3 times 3 times 7 = 2^1 times 3^2 times 7^1]

Рассмотрим, например, такую задачу:

Условие: Нужно разбить (N) людей на группы равного размера. Нам интересно, какие размеры это могут быть.

Решение: По сути нас просят найти число делителей (N). Нужно посмотреть на разложение числа (N) на простые множители, в общем виде оно выглядит так:

[N= p_1^{a_1} times p_2^{a_2} times ldots times p_k^{a_k}]

Теперь подумаем над этим выражением с точки зрения комбинаторики. Чтобы «сгенерировать» какой-нибудь делитель, нужно подставить в степень (i)-го простого число от 0 до (a_i) (то есть (a_i+1) различное значение), и так для каждого. То есть делитель (N) выглядит ровно так: [M= p_1^{b_1} times p_2^{b_2} times ldots times p_k^{b_k}, 0 leq b_i leq a_i] Значит, ответом будет произведение ((a_1+1) times (a_2+1) times ldots times (a_k + 1)).

Алгоритм разложения на простые множители

Применяя алгоритм проверки числа на простоту, мы умеем легко находить минимальный простой делитель числа N. Ясно, что как только мы нашли простой делитель числа (N), мы можем число (N) на него поделить и продолжить искать новый минимальный простой делитель.

Будем перебирать простой делитель от (2) до корня из (N) (как и раньше), но в случае, если (N) делится на этот делитель, будем просто на него делить. Причем, возможно, нам понадобится делить несколько раз ((N) может делиться на большую степень этого простого делителя). Так мы будем набирать простые делители и остановимся в тот момент, когда (N) стало либо (1), либо простым (и мы остановились, так как дошли до корня из него). Во втором случае надо еще само (N) добавить в ответ.

Напишем алгоритм факторизации:

def factorize(n):
    factors = []
    i = 2
    while i * i <= n: # перебираем простой делитель
        while n % i == 0: # пока N на него делится
            n //= i # делим N на этот делитель
            factors.append(i)
        i += 1
    # возможно, в конце N стало большим простым числом,
    # у которого мы дошли до корня и поняли, что оно простое
    # его тоже нужно добавить в разложение
    if n > 1:
        factors.append(n)
    return factors

for i in [1, 2, 3, 10, 11, 12, 10**9+6, 10**9+7]:
    print(i, '=', ' x '.join(str(x) for x in factorize(i)))

1 = 
2 = 2
3 = 3
10 = 2 x 5
11 = 11
12 = 2 x 2 x 3
1000000006 = 2 x 500000003
1000000007 = 1000000007

Задание

За сколько работает этот алгоритм?

.

.

.

.

Решение

За те же самые (O(sqrt{N})). Итераций цикла while с перебором делителя будет не больше, чем (sqrt{N}). Причем ровно (sqrt{N}) операций будет только в том случае, если (N) — простое.

А итераций деления (N) на делители будет столько, сколько всего простых чисел в факторизации числа (N). Понятно, что это не больше, чем (O(log{N})).

Задание

Докажите, что число (N) имеет не больше, чем (O(log{N})) простых множителей в факторизации.

Разные свойства простых чисел*

Вообще, про простые числа известно много свойств, но почти все из них очень трудно доказать. Вот еще некоторые из них:

• Простых чисел, меньших (N), примерно (frac{N}{ln N}).
• N-ое простое число равно примерно (Nln N).
• Простые числа распределены более-менее равномерно. Например, если вам нужно найти какое-то простое число в промежутке, то можно их просто перебрать и проверить — через несколько сотен какое-нибудь найдется.
• Для любого (N ge 2) на интервале ((N, 2N)) всегда найдется простое число (Постулат Бертрана)
• Впрочем, существуют сколь угодно длинные отрезки, на которых простых чисел нет. Самый простой способ такой построить — это начать с (N! + 2).
• Есть алгоритмы, проверяющие число на простоту намного быстрее, чем за корень.
• Максимальное число делителей равно примерно (O(sqrt[3]{n})). Это не математический результат, а чисто эмпирический — не пишите его в асимптотиках.
• Максимальное число делителей у числа на отрезке ([1, 10^5]) — 128
• Максимальное число делителей у числа на отрекзке ([1, 10^9]) — 1344
• Максимальное число делителей у числа на отрезке ([1, 10^{18}]) — 103680
• Наука умеет факторизовать числа за (O(sqrt[4]{n})), но об этом как-нибудь в другой раз.
• Любое число больше трёх можно представить в виде суммы двух простых (гипотеза Гольдбаха), но это не доказано.

Решето Эратосфена

Часто нужно не проверять на простоту одно число, а найти все простые числа до (N). В этом случае наивный алгоритм будет работать за (O(Nsqrt N)), так как нужно проверить на простоту каждое число от 1 до (N).

Но древний грек Эратосфен предложил делать так:

Запишем ряд чисел от 1 до (N) и будем вычеркивать числа: * делящиеся на 2, кроме самого числа 2 * затем деляющиеся на 3, кроме самого числа 3 * затем на 5, затем на 7, и так далее и все остальные простые до n. Таким образом, все незачеркнутые числа будут простыми — «решето» оставит только их.

Красивая визуализация

Задание

Найдите этим способом на бумажке все простые числа до 50, потом проверьте с программой:

N = 50
prime = [1] * (N + 1)
prime[0], prime[1] = 0, 0
for i in range(2, N + 1): # можно и до sqrt(N)
    if prime[i]:
        for j in range(2 * i, N + 1, i): # идем с шагом i, можно начиная с i * i
            prime[j] = 0
for i in range(1, N + 1):
    if prime[i]:
        print(i)

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47

У этого алгоритма можно сразу заметить несколько ускорений.

Во-первых, число (i) имеет смысл перебирать только до корня из (N), потому что при зачеркивании составных чисел, делящихся на простое (i > sqrt N), мы ничего не зачеркнем. Почему? Пусть существует составное (M leq N), которое делится на %i%, и мы его не зачеркнули. Но тогда (i > sqrt N geq sqrt M), а значит по ранее нами доказанному утверждению (M) должно делиться и на простое число, которое меньше корня. Но это значит, что мы его уже вычеркнули.

Во-вторых, по этой же самое причине (j) имеет смысл перебирать только начиная с (i^2). Зачем вычеркивать (2i), (3i), (4i), …, ((i-1)i), если они все уже вычеркнуты, так как мы уже вычеркивали всё, что делится на (2), (3), (4), …, ((i-1)).

Асимптотика

Такой код будет работать за (O(N log log N)) по причинам, которые мы пока не хотим объяснять формально.

Гармонический ряд

Научимся оценивать асимптотику величины (1 + frac{1}{2} + ldots + frac{1}{N}), которая нередко встречается в задачах, где фигурирует делимость.

Возьмем (N) равное (2^i — 1) и запишем нашу сумму следующим образом: [left(frac{1}{1}right) + left(frac{1}{2} + frac{1}{3}right) + left(frac{1}{4} + ldots + frac{1}{7}right) + ldots + left(frac{1}{2^{i — 1}} + ldots + frac{1}{2^i — 1}right)]

Каждое из этих слагаемых имеет вид [frac{1}{2^j} + ldots + frac{1}{2^{j + 1} — 1} le frac{1}{2^j} + ldots + frac{1}{2^j} = 2^j frac{1}{2^j} = 1]

Таким образом, наша сумма не превосходит (1 + 1 + ldots + 1 = i le 2log_2(2^i — 1)). Тем самым, взяв любое (N) и дополнив до степени двойки, мы получили асимптотику (O(log N)).

Оценку снизу можно получить аналогичным образом, оценив каждое такое слагаемое снизу значением (frac{1}{2}).

Попытка объяснения асимптотики** (для старших классов)

Мы знаем, что гармонический ряд (1 + frac{1}{2} + frac{1}{3} + ldots + frac{1}{N}) это примерно (log N), а значит [N + frac{N}{2} + frac{N}{3} + ldots + frac{N}{N} sim N log N]

А что такое асимптотика решета Эратосфена? Мы как раз ровно (frac{N}{p}) раз зачеркиваем числа делящиеся на простое число (p). Если бы все числа были простыми, то мы бы как раз получили (N log N) из формули выше. Но у нас будут не все слагаемые оттуда, только с простым (p), поэтому посмотрим чуть более точно.

Известно, что простых чисел до (N) примерно (frac{N}{log N}), а значит допустим, что k-ое простое число примерно равно (k ln k). Тогда

[sum_{substack{2 leq p leq N \ text{p is prime}}} frac{N}{p} sim frac{1}{2} + sum_{k = 2}^{frac{N}{ln N}} frac{N}{k ln k} sim int_{2}^{frac{N}{ln N}} frac{N}{k ln k} dk =N(lnlnfrac{N}{ln N} — lnln 2) sim N(lnln N — lnlnln N) sim N lnln N]

Но вообще-то решето можно сделать и линейным.

Задание

Решите 5 первых задач из этого контеста:

https://informatics.msk.ru/mod/statements/view.php?id=34271

Линейное решето Эратосфена*

Наша цель — для каждого числа до (N) посчитать его минимальный простой делитель. Будем хранить его в массиве min_d. Параллельно будем хранить и список всех найденных простых чисел primes — это ровно те числа (x), у которых (min_d[x] = x).

Основное утверждение такое:

Пусть у числа (M) минимальный делитель равен (a). Тогда, если (M) составное, мы хотим вычеркнуть его ровно один раз при обработке числа (frac{M}{a}).

Мы также перебираем число (i) от (2) до (N). Если (min_d[i]) равно 0 (то есть мы не нашли ни один делитель у этого числа еще), значит оно простое — добавим в primes и сделаем (min_d[i] = i).

Далее мы хотим вычеркнуть все числа (i times k) такие, что (k) — это минимальный простой делитель этого числа. Из этого следует, что необходимо и достаточно перебрать (k) в массиве primes, и только до тех пор, пока (k < min_d[i]). Ну и перестать перебирать, если (i times k > N).

Алгоритм пометит все числа по одному разу, поэтому он корректен и работает за (O(N)).

N = 30
primes = []
min_d = [0] * (N + 1)

for i in range(2, N + 1):
    if min_d[i] == 0:
        min_d[i] = i
        primes.append(i)
    for p in primes:
        if p > min_d[i] or i * p > N:
            break
        min_d[i * p] = p
    print(i, min_d)
print(min_d)
print(primes)

2 [0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
3 [0, 0, 2, 3, 2, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
4 [0, 0, 2, 3, 2, 0, 2, 0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
5 [0, 0, 2, 3, 2, 5, 2, 0, 2, 3, 2, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0]
6 [0, 0, 2, 3, 2, 5, 2, 0, 2, 3, 2, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0]
7 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 0, 2, 0, 2, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 5, 0, 0, 0, 0, 0]
8 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 0, 0, 0, 3, 0, 0, 0, 5, 0, 0, 0, 0, 0]
9 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 0, 3, 0, 0, 0, 5, 0, 3, 0, 0, 0]
10 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 0, 0, 0, 5, 0, 3, 0, 0, 0]
11 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 0, 5, 0, 3, 0, 0, 0]
12 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 0, 3, 0, 0, 0]
13 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 0, 0, 0]
14 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 0]
15 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
16 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
17 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
18 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
19 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
20 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
21 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
22 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2]
23 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2]
24 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2]
25 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2]
26 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2]
27 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2]
28 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2]
29 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2]
30 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2]
[0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Этот алгоритм работает асимптотически быстрее, чем обычное решето. Но на практике, если писать обычное решето Эратсфена с оптимизациями, то оно оказывается быстрее линейнего. Также линейное решето занимает гораздо больше памяти — ведь в обычном решете можно хранить просто (N) бит, а здесь нам нужно (N) чисел и еще массив primes.

Зато один из «побочных эффектов» алгоритма — он неявно вычисляет факторизацию всех чисел от (1) до (N). Ведь зная минимальный простой делитель любого числа от (1) до (N) можно легко поделить на это число, посмотреть на новый минимальный простой делитель и так далее.

НОД и НОК

Введем два определения.

Наибольший общий делитель (НОД) чисел (a_1, a_2, ldots, a_n) — это максимальное такое число (x), что все (a_i) делятся на (x).

Наименьшее общее кратное (НОК) чисел (a_1, a_2, ldots, a_n) — это минимальное такое число (x), что (x) делится на все (a_i).

Например, * НОД(18, 30) = 6 * НОД(60, 180, 315) = 15 * НОД(1, N) = 1 * НОК(12, 30) = 6 * НОК(1, 2, 3, 4) = 12 * НОК(1, (N)) = (N)

Зачем они нужны? Например, они часто возникают в задачах.

Условие: Есть (N) шестеренок, каждая (i)-ая зацеплена с ((i-1))-ой. (i)-ая шестеренка имеет (a_i) зубчиков. Сколько раз нужно повернуть полносьтю первую шестеренку, чтобы все остальные шестеренки тоже вернулись на изначальное место?

Решение: Когда одна шестеренка крутится на 1 зубчик, все остальные тоже крутятся на один зубчик. Нужно найти минимальное такое число зубчиков (x), что при повороте на него все шестеренки вернутся в изначальное положение, то есть (x) делится на все (a_i), то есть это НОК((a_1, a_2, ldots, a_N)). Ответом будет (frac{x}{a_1}).

Еще пример задачи на применение НОД и НОК:

Условие: Город — это прямоугольник (n) на (m), разделенный на квадраты единичного размера. Вертолет летит из нижнего левого угла в верхний правый по прямой. Вертолет будит людей в квартале, когда он пролетает строго над его внутренностью (границы не считаются). Сколько кварталов разбудит вертолёт?

Решение: Вертолет пересечет по вертикали ((m-1)) границу. С этим ничего не поделать — каждое считается как новое посещение какого-то квартала. По горизонтали то же самое — ((n-1)) переход в новую ячейку будет сделан.

Однако еще есть случай, когда он пересекает одновременно обе границы (то есть пролетает над каким-нибудь углом) — ровно тот случай, когда нового посещения квартала не происходит. Сколько таких будет? Ровно столько, сколько есть целых решений уравнения (frac{n}{m} = frac{x}{y}). Мы как бы составили уравнение движения вертолёта и ищем, в скольки целых точках оно выполняется.

Пусть (t = НОД(n, m)), тогда (n = at, m = bt).

Тогда (frac{n}{m} = frac{a}{b} = frac{x}{y}). Любая дробь с натуральными числителем и знаменателем имеет ровно одно представление в виде несократимой дроби, так что (x) должно делиться на (a), а (y) должно делиться на (b). А значит, как ответ подходят ((a, b), (2a, 2b), (3a, 3b), cdots, ((t-1)a, (t-1)b)). Таких ответов ровно (t = НОД(n, m))

Значит, итоговый ответ: ((n-1) + (m-1) — (t-1)).

Кстати, когда (НОД(a, b) = 1), говорят, что (a) и (b) взаимно просты.

Алгоритм Евклида

Осталось придумать, как искать НОД и НОК. Понятно, что их можно искать перебором, но мы хотим хороший быстрый способ.

Давайте для начала научимся искать (НОД(a, b)).

Мы можем воспользоваться следующим равенством: [НОД(a, b) = НОД(a, b — a), b > a]

Оно доказывается очень просто: надо заметить, что множества общих делителей у пар ((a, b)) и ((a, b — a)) совпадают. Почему? Потому что если (a) и (b) делятся на (x), то и (b-a) делится на (x). И наоборот, если (a) и (b-a) делятся на (x), то и (b) делится на (x). Раз множства общих делитей совпадают, то и максимальный делитель совпадает.

Из этого равенства сразу следует следующее равенство: [НОД(a, b) = НОД(a, b operatorname{%} a), b > a]

(так как (НОД(a, b) = НОД(a, b — a) = НОД(a, b — 2a) = НОД(a, b — 3a) = ldots = НОД(a, b operatorname{%} a)))

Это равенство дает идею следующего рекурсивного алгоритма:

[НОД(a, b) = НОД(b operatorname{%} a, a) = НОД(a operatorname{%} , (b operatorname{%} a), b operatorname{%} a) = ldots]

Например: [НОД(93, 36) = ] [= НОД(36, 93spaceoperatorname{%}36) = НОД(36, 21) = ] [= НОД(21, 15) = ] [= НОД(15, 6) = ] [= НОД(6, 3) = ] [= НОД(3, 0) = 3]

Задание:

Примените алгоритм Евклида и найдите НОД чисел: * 1 и 500000 * 10, 20 * 18, 60 * 55, 34 * 100, 250

По-английски наибольший общий делитель — greatest common divisor. Поэтому вместо НОД будем в коде писать gcd.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(1, 500000))
print(gcd(10, 20))
print(gcd(18, 60))
print(gcd(55, 34))
print(gcd(100, 250))
print(gcd(2465473782, 12542367456))

1
10
6
1
50
6

Вообще, в C++ такая функция уже есть в компиляторе g++ — называется __gcd. Если у вас не Visual Studio, то, скорее всего, у вас g++. Вообще, там много всего интересного.

А за сколько оно вообще работает?

Задание

Докажите, что алгоритм Евклида для чисел (N), (M) работает за (O(log(N+M))).

Кстати, интересный факт: самыми плохими входными данными для алгоритма Евклида являются числа Фибоначчи. Именно там и достигается логарифм.

Как выразить НОК через НОД

(НОК(a, b) = frac{ab}{НОД(a, b)})

По этой формуле можно легко найти НОК двух чисел через их произведение и НОД. Почему она верна?

Посмотрим на разложения на простые множители чисел a, b, НОК(a, b), НОД(a, b).

[ a = p_1^{a_1}times p_2^{a_2}timesldotstimes p_n^{a_n} ] [ b = p_1^{b_1}times p_2^{b_2}timesldotstimes p_n^{b_n} ] [ ab = p_1^{a_1+b_1}times p_2^{a_2+b_2}timesldotstimes p_n^{a_n+b_n} ]

Из определений НОД и НОК следует, что их факторизации выглядят так: [ НОД(a, b) = p_1^{min(a_1, b_1)}times p_2^{min(a_2, b_2)}timesldotstimes p_n^{min(a_n, b_n)} ] [ НОК(a, b) = p_1^{max(a_1, b_1)}times p_2^{max(a_2, b_2)}timesldotstimes p_n^{max(a_n, b_n)} ]

Тогда посчитаем (НОД(a, b) times НОК(a, b)): [ НОД(a, b)НОК(a, b) = p_1^{min(a_1, b_1)+max(a_1, b_1)}times p_2^{min(a_2, b_2)+max(a_2, b_2)}timesldotstimes p_n^{min(a_n, b_n)+max(a_n, b_n)} =] [ = p_1^{a_1+b_1}times p_2^{a_2+b_2}timesldotstimes p_n^{a_n+b_n} = ab]

Формула доказана.

Как посчитать НОД/НОК от более чем 2 чисел

Для того, чтобы искать НОД или НОК у более чем двух чисел, достаточно считать их по цепочке:

(НОД(a, b, c, d, ldots) = НОД(НОД(a, b), c, d, ldots))

(НОК(a, b, c, d, ldots) = НОК(НОК(a, b), c, d, ldots))

Почему это верно?

Ну просто множество общих делителей (a) и (b) совпадает с множеством делителей (НОД(a, b)). Из этого следует, что и множество общих делителей (a), (b) и еще каких-то чисел совпадает с множеством общих делителей (НОД(a, b)) и этих же чисел. И раз совпадают множества общих делителей, то и наибольший из них совпадает.

С НОК то же самое, только фразу “множество общих делителей” надо заменить на “множество общих кратных”.

Задание

Решите задачи F, G, H, I из этого контеста:

https://informatics.msk.ru/mod/statements/view.php?id=34271

Расширенный алгоритм Евклида*

Очень важным для математики свойством наибольшего общего делителя является следующий факт:

Для любых целых (a, b) найдутся такие целые (x, y), что (ax + by = d), где (d = gcd(a, b)).

Из этого следует, что существует решение в целых числах, например, у таких уравнений: * (8x + 6y = 2) * (4x — 5y = 1) * (116x + 44y = 4) * (3x + 11y = -1)

Мы сейчас не только докажем, что решения у таких уравнений существуют, но и приведем быстрый алгоритм нахождения этих решений. Здесь нам вновь пригодится алгоритм Евклида.

Рассмотрим один шаг алгоритма Евклида, преобразующий пару ((a, b)) в пару ((b, a operatorname{%} b)). Обозначим (r = a operatorname{%} b), то есть запишем деление с остатком в виде (a = bq + r).

Предположим, что у нас есть решение данного уравнения для чисел (b) и (r) (их наибольший общий делитель, как известно, тоже равен (d)): [bx_0 + ry_0 = d]

Теперь сделаем в этом выражении замену (r = a — bq):

[bx_0 + ry_0 = bx_0 + (a — bq)y_0 = ay_0 + b(x_0 — qy_0)]

Tаким образом, можно взять (x = y_0), а (y = (x_0 — qy_0) = (x_0 — (a operatorname{/} b)y_0)) (здесь (/) обозначает целочисленное деление).

В конце алгоритма Евклида мы всегда получаем пару ((d, 0)). Для нее решение требуемого уравнения легко подбирается — (d * 1 + 0 * 0 = d). Теперь, используя вышесказанное, мы можем идти обратно, при вычислении заменяя пару ((x, y)) (решение для чисел (b) и (a operatorname{%} b)) на пару ((y, x — (a / b)y)) (решение для чисел (a) и (b)).

Это удобно реализовывать рекурсивно:

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    d, x, y = extended_gcd(b, a % b)
    return d, y, x - (a // b) * y

a, b = 3, 5
res = extended_gcd(a, b)
print("{3} * {1} + {4} * {2} = {0}".format(res[0], res[1], res[2], a, b))

3 * 2 + 5 * -1 = 1

Но также полезно и посмотреть, как будет работать расширенный алгоритм Евклида и на каком-нибудь конкретном примере. Пусть мы, например, хотим найти целочисленное решение такого уравнения: [116x + 44y = 4] [(2times44+28)x + 44y = 4] [44(2x+y) + 28x = 4] [44x_0 + 28y_0 = 4] Следовательно, [x = y_0, y = x_0 — 2y_0] Будем повторять такой шаг несколько раз, получим такие уравнения: [116x + 44y = 4] [44x_0 + 28y_0 = 4, x = y_0, y = x_0 — 2y_0] [28x_1 + 16y_1 = 4, x_0 = y_1, y_0 = x_1 — y_1] [16x_2 + 12y_2 = 4, x_1 = y_2, y_1 = x_2 — y_2] [12x_3 + 4y_3 = 4, x_2 = y_3, y_2 = x_3 — y_3] [4x_4 + 0y_4 = 4, x_3 = y_4, y_3 = x_4 — 3 y_4] А теперь свернем обратно: [x_4 = 1, y_4 = 0] [x_3 = 0, y_3 =1] [x_2 = 1, y_2 =-1] [x_1 = -1, y_1 =2] [x_0 = 2, y_0 =-3] [x = -3, y =8]

Действительно, (116times(-3) + 44times8 = 4)

Задание

Решите задачу J из этого контеста:

https://informatics.msk.ru/mod/statements/view.php?id=34273

Операции по модулю

Выражение (a equiv b pmod m) означает, что остатки от деления (a) на (m) и (b) на (m) равны. Это выражение читается как «(a) сравнимо (b) по модулю (m)».

Еще это можно опрделить так: (a) сравнимо c (b) по модулю (m), если ((a — b)) делится на (m).

Все целые числа можно разделить на классы эквивалентности — два числа лежат в одном классе, если они сравнимы по модулю (m). Говорят, что мы работаем в «кольце остатков по модулю (m)», и в нем ровно (m) элементов: (0, 1, 2, cdots, m-1).

Сложение, вычитение и умножение по модулю определяются довольно интуитивно — нужно выполнить соответствующую операцию и взять остаток от деления.

С делением намного сложнее — поделить и взять по модулю не работает. Об этом подробнее поговорим чуть дальше.

a = 30
b = 50
mod = 71

print('{} + {} = {} (mod {})'.format(a, b, (a + b) % mod, mod))
print('{} - {} = {} (mod {})'.format(a, b, (a - b) % mod, mod)) # на C++ это может не работать, так как модуль от отрицательного числа берется странно
print('{} - {} = {} (mod {})'.format(a, b, (a - b + mod) % mod, mod)) # на C++ надо писать так, чтобы брать модулю от гарантированно неотрицательного числа
print('{} * {} = {} (mod {})'.format(a, b, (a * b) % mod, mod))
# print((a / b) % mod) # а как писать это, пока неясно

30 + 50 = 9 (mod 71)
30 - 50 = 51 (mod 71)
30 - 50 = 51 (mod 71)
30 * 50 = 9 (mod 71)

Задание

Посчитайте: * (2 + 3 pmod 5) * (2 * 3 pmod 5) * (2 ^ 3 pmod 5) * (2 — 4 pmod 5) * (5 + 5 pmod 6) * (2 * 3 pmod 6) * (3 * 3 pmod 6)

Для умножения (в C++) нужно ещё учитывать следующий факт: при переполнении типа всё ломается (разве что если вы используете в качестве модуля степень двойки).

• int вмещает до (2^{31} — 1 approx 2 cdot 10^9).
• long long вмещает до (2^{63} — 1 approx 8 cdot 10^{18}).
• long long long в плюсах нет, при попытке заиспользовать выдает ошибку long long long is too long.
• Под некоторыми компиляторами и архитектурами доступен int128, но не везде и не все функции его поддерживают (например, его нельзя вывести обычными методами).

Зачем нужно считать ответ по модулю

Очень часто в задаче нужно научиться считать число, которое в худшем случае гораздо больше, чем (10^{18}). Тогда, чтобы не заставлять вас писать длинную арифметику, автор задачи часто просит найти ответ по модулю большого числа, обычно (10^9 + 7)

Кстати, вместо того, чтобы писать (1000000007) удобно просто написать (1e9 + 7). (1e9) означает (1 times 10^9)

int mod = 1e9 + 7; # В C++
cout << mod;

1000000007

N = 1e9 + 7 # В питоне такое число становится float
print(N)
print(int(N))

1000000007.0
1000000007

Быстрое возведение в степень

Задача: > Даны натуральные числа (a, b, c < 10^9). Найдите (a^b) (mod (c)).

Мы хотим научиться возводить число в большую степень быстро, не просто умножая (a) на себя (b) раз. Требование на модуль здесь дано только для того, чтобы иметь возможность проверить правильность алгоритма для чисел, которые не влезают в int и long long.

Сам алгоритм довольно простой и рекурсивный, постарайтесь его придумать, решая вот такие примеры (прямо решать необязательно, но можно придумать, как посчитать значение этих чисел очень быстро):

• (3^2)
• (3^4)
• (3^8)
• (3^{16})
• (3^{32})
• (3^{33})
• (3^{66})
• (3^{132})
• (3^{133})
• (3^{266})
• (3^{532})
• (3^{533})
• (3^{1066})

Да, здесь специально приведена такая последовательность, в которой каждое следующее число легко считается через предыдущее: его либо нужно умножить на (a=3), либо возвести в квадрат. Так и получается рекурсивный алгоритм:

• (a^0 = 1)
• (a^{2k}=(a^{k})^2)
• (a^{2k+1}=a^{2k}times a)

Нужно только после каждой операции делать mod: * (a^0 pmod c = 1) * (a^{2k} pmod c = (a^{k} pmod c)^2 pmod c) * (a^{2k+1} pmod c = ((a^{2k}pmod c) times a) pmod c)

Этот алгоритм называется быстрое возведение в степень. Он имеет много применений: * в криптографии очень часто надо возводить число в большую степень по модулю * используется для деления по простому модулю (см. далее) * можно быстро перемножать не только числа, но еще и матрицы (используется для динамики, например)

Асимптотика этого алгоритма, очевидно, (O(log c)) — за каждые две итерации число уменьшается хотя бы в 2 раза.

Задание

Решите задачу K из этого контеста:

https://informatics.msk.ru/mod/statements/view.php?id=34271

Задание

Решите как можно больше задач из практического контеста:

https://informatics.msk.ru/mod/statements/view.php?id=34273

Деление по модулю*

Давайте все-таки научимся не только умножать, но и делить по простому модулю. Вот только что это значит?

(a / b) = (a times b^{-1}), где (b^{-1}) — это обратный элемент к (b).

Определение: (b^{-1}) — это такое число, что (bb^{-1} = 1)

Утверждение: в кольце остатков по простому модулю (p) у каждого остатка (кроме 0) существует ровно один обратный элемент.

Например, обратный к (2) по модулю (5) это (3) ((2 times 3 = 1 pmod 5)))

Задание

Найдите обратный элемент к: * числу (3) по модулю (5) * числу (3) по модулю (7) * числу (1) по модулю (7) * числу (2) по модулю (3) * числу (9) по модулю (31)

Давайте докажем это утверждение: надо заметить, что если каждый ненулевой остаток (1, 2, ldots, (p-1)) умножить на ненулевой остаток (a), то получатся числа (a, 2a, ldots, (p-1)a) — и они все разные! Они разные, потому что если (xa = ya), то ((x-y)a = 0), а значит ((x — y) a) делится на (p), (a) — ненулевой остаток, а значит (x = y), и это не разные числа. И из того, что все числа получились разными, это все ненулевые, и их столько же, следует, что это ровно тот же набор чисел, просто в другом порядке!

Из этого следует, что среди этих чисел есть (1), причем ровно один раз. А значит существует ровно один обратный элемент (a^{-1}). Доказательство закончено.

Это здорово, но этот обратный элемент еще хочется быстро находить. Быстрее, чем за (O(p)).

Есть несколько способов это сделать.

Через малую теорему Ферма

Малая теорема Ферма: > (a^{p-1} = 1 pmod p), если (p) — простое, (a neq 0 pmod p)).

Доказательство: В предыдущем пункте мы выяснили, что множества чисел (1, 2, ldots, (p-1)) и (a, 2a, ldots, (p-1)a) совпадают. Из этого следует, что их произведения тоже совпадают по модулю: ((p-1)! = a^{p-1} (p-1)! pmod p).

((p-1)!neq 0 pmod p) а значит на него можно поделить (это мы кстати только в предыдущем пункте доказали, поделить на число — значит умножить на обратный к нему, который существует).

А значит, (a^{p — 1} = 1 pmod p).

Как это применить Осталось заметить, что из малой теоремы Ферма сразу следует, что (a^{p-2}) — это обратный элемент к (a), а значит мы свели задачу к возведению (a) в степень (p-2), что благодаря быстрому возведению в степень мы умеем делать за (O(log p)).

Обобщение У малой теоремы Ферма есть обобщение для составных (p):

Теорема Эйлера: > (a^{varphi(p)} = 1 pmod p), (a) — взаимно просто с (p), а (varphi(p)) — это функция Эйлера (количество чисел, меньших (p) и взаимно простых с (p)).

Доказывается теорема очень похоже, только вместо ненулевых остатков (1, 2, ldots, p-1) нужно брать остатки, взаимно простые с (p). Их как раз не (p-1), а (varphi(p)).

Для нахождения обратного по этой теореме достаточно посчитать функцию Эйлера (varphi(p)) и найти (a^{-1} = a^{varphi(p) — 1}).

Но с этим возникают большие проблемы: посчитать функцию Эйлера сложно. Более того, на предполагаемой невозможности быстро ее посчитать построены некоторые криптографические алгоритм типа RSA. Поэтому быстро делить по составному модулю этим способом не получится.

Через расширенный алгоритм Евклида

Этим способом легко получится делить по любому модулю! Рекомендую.

Пусть мы хотим найти (a^{-1} pmod p), (a) и (p) взаимно простые (а иначе обратного и не будет существовать).

Давайте найдем корни уравнения

[ax + py = 1]

Они есть и находятся расширенным алгоритмом Евклида за (O(log p)), так как (НОД(a, p) = 1), ведь они взаимно простые.

Тогда если взять остаток по модулю (p):

[ax = 1 pmod p]

А значит, найденный (x) и будет обратным элементом к (a).

То есть надо просто найти (x) из решения того уравнения по модулю (p). Можно брать по модулю прямо походу решения уравнения, чтобы случайно не переполниться.

Тема 25.

Программирование — Обработка целочисленной информации

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.

Готовиться с нами — ЛЕГКО!

Подтемы раздела

программирование — обработка целочисленной информации

Решаем задачи

Показать ответ и решение

Если число имеет разложение вида … , то количество чётных делителей такого числа равно
… (выбрали степень двойки от до , степень каждого простого от до ). По
условию это равно — простое число, как произведение натуральных чисел его можно представить как или
.

Случай : , все число равно , не подходит.

Случай : , какое-то , все остальные — приходим к разложению вида .

На частном случае решение будет выглядеть так:

С помощью стандартной программы найдем подходящие нам числа до для того, чтобы рассмотреть
их:

def dividers(n):
    k = 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if i % 2 == 0:
                k += 1
            if (n // i) % 2 == 0 and n // i != i:
                k += 1
    return k

for i in range(1, 100000):
    if dividers(i) == 7:
        print(i)

Подходящие нам числа в диапазоне до — это , и . Хочется разложить эти
числа:

Заметим, что все числа раскладываются на , где — простое число.

Воспользуемся выведенной формулой для решения:

def prime(x):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

ans = 0
for i in range(int((33333333 // 2)**(1/6)), int((333333333 // 2)**(1/6)) + 1):
    if prime(i):
        if 33333333 <= 2*(i**6) <= 333333333:
            ans += 1
print(ans)

Найдите все натуральные числа, принадлежащие отрезку [22 333 888; 88 999 888], у которых ровно различных
нечётных делителя (количество чётных делителей может быть любым). В ответе укажите количество данных
чисел.

Показать ответ и решение

def is_prime(n):
    if n <= 1:
        return False
    for j in range(2, int(n ** 0.5) + 1):
        if n % j == 0:
            return False
    return True

ans = 0
for j in range(3, 10000):
    if is_prime(j):
        for i in range(26):
            if 22333888 <= 2**i*j**2 <= 88999888:
                ans += 1
print(ans)

Найдите все натуральные числа, принадлежащие отрезку [11 111 111; 77 777 777], у которых ровно различных
делителей. В ответе укажите количество данных чисел.

Показать ответ и решение

def prime(x):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

ans = 0
for i in range(int(11111111**0.25), int((77777777+1)**0.25)+1):
    if prime(i):
        ans += 1
print(ans)

Напишите программу, которая получает на вход число и возвращает количество его делителей. В ответе укажите
количество делителей для числа .

Показать ответ и решение

Решение 1

count = 0
x = int(input())
for i in range(1, int(x ** 0.5) + 1):
    if x % i == 0:
        count += 1
        if x // i != i:
            count += 1
print(count)

Решение 2

a = set()
x = int(input())
for i in range(1, int(x ** 0.5) + 1):
    if x % i == 0:
        a.add(i)
        a.add(x // i)
print(len(a))

Показать ответ и решение

a = [1, 2, 98, 43, 89, 739]
x = 1052336
summa = 0
for i in a:
    if x % i == 0:
        summa += x // i
print(summa)

Показать ответ и решение

Обратим внимание, что если — делитель числа , то и — делитель числа . Очевидно, эти два числа находятся
по разную сторону от (иначе, предположим, что они оба меньше, тогда чего явно не
может быть, случай, когда оба больше — аналогичен). Таким образом, мы видим, что все делители разбиваются на пары, в
которых один делитель меньше корня, а другой — больше. Отсюда понимаем, что делителей, меньших корня столько же,
сколько и больших.

print(0)

А теперь представим, что мы не знаем математику, и попробуем решить это другим способом:

x = 3052336
sq = x ** 0.5
more = 0
less = 0
for i in range(1, x + 1):
    if x % i == 0:
        if i > sq:
            more += 1
        if i < sq:
            less += 1
print(more - less)

Утверждается, что количество делителей числа четно. Найдите количество пар делителей числа ,
произведение которых равно исходному числу. При этом пары делителей выбираются следующим образом минимальный
делитель * максимальный делитель, предминимальный делитель * предмаксимальный делитель и т.д. В ответе укажите
два числа через пробел: сначала количество рассматриваемых пар, затем количеством пар, произведение которых равно
исходному числу.

Показать ответ и решение

a = []
x = 2052336
for i in range(1, x + 1):
    if x % i == 0:
        a.append(i)
count = 0
n = len(a)
for i in range(n // 2):
    if a[i] * a[n - i - 1] == x:
        count += 1
print(n // 2, count)

Назовём числа и числами-близнецами, если .

Найдите наименьшее натуральное число, имеющее ровно 512 делителей, простые делители которого образуют не менее
трёх пар чисел-близнецов. В ответе укажите число, а также все его простые делители.

Показать ответ и решение

from itertools import combinations_with_replacement


def prime(x):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True


def count_del(x):
    ans = []
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            ans += [i]
            ans += [x // i]
    return sorted(list(set(ans)))


def check(a):
    ans = 1
    for i in range(len(a)):
        ans *= a[i]
        if ans > 512:
            return False
    return ans == 512


dels = count_del(512)
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
# Если скобок 9 штук и каждое альфа равно 1
minim = 2 ** 511
# Если скобок 9 штук и каждое альфа равно 1
t = 1
degrees = [2] * 9
for k in range(len(degrees)):
    t *= (primes[k] ** (degrees[k] - 1))
minim = min(minim, t)
# Все остальные случаи
                                                                                                     
                                                                                                     
for j in range(2, 9):
    for i in combinations_with_replacement(dels, j):
        if check(i):
            t = 1
            degrees = i[::-1]
            for k in range(len(degrees)):
                t = t * (primes[k] ** (degrees[k] - 1))
            minim = min(minim, t)
print(minim, *[i for i in count_del(minim) if prime(i)])

Ответ:

17297280 2 3 5 7 11 13

Найдите максимальное число на отрезке [1010101; 101010101], имеющее ровно 128 делителей, которое будет кратно
16. Выведите на экран в первой строке найденное число, а во второй все его нечетные делители в порядке
возрастания.

Показать ответ и решение

def count_del(x):
    ans = [1, x]
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            ans += [i]
            if i != x // i:
                ans += [x//i]
        if len(ans) > 128:
            return ans
    return ans
for i in range(101010101, 1010101-1, -1):
    if len(count_del(i)) == 128 and i % 16 == 0:
        print(i, *sorted([i for i in count_del(i) if i % 2 != 0]))
        break

Ответ:

101008512 1 3 9 11 27 33 99 297 2657 7971 23913 29227 71739 87681 263043 789129

Найдите пять последних натуральных чисел на отрезке , которые имеет ровно делителя. В ответе
укажите подходящие числа в порядке возрастания.

Показать ответ и решение

def count_del(x):
    count = 2
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            count += 1
            if i != x // i:
                count += 1
        if count > 64:
            return False
    return count == 64
ans = []
for i in range(101010101, 1010101-1, -1):
    if count_del(i):
        ans += [i]
    if len(ans) == 5:
        print(*sorted(ans))
        break

Ответ:

101009928

101009937

101009958

101010024

101010090

Найдите наибольшее натуральное число на отрезке , которое имеет ровно делителей. В ответе укажите
число.

Показать ответ и решение

def divs(n):
    count = 0
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            count += 1
            if i!=n//i:
                count += 1
    return count
for x in range(5000000, 10000 - 1, -1):
    if divs(x) == 10:
        print(x)
        break

Найдите наименьшее натуральное число, которое имеет ровно делителей. В ответе укажите число.

Показать ответ и решение

from itertools import combinations_with_replacement
 
def prime(x):
 
    for i in range(2, int(x**0.5)+1):
 
        if x % i == 0:
 
            return False
 
    return True
 
def count_del(x):
 
    ans = []
 
    for i in range(2, int(x**0.5)+1):
 
        if x % i == 0:
 
            ans += [i]
 
            ans += [x//i]
 
    return sorted(list(set(ans)))
 
def check(a):
 
    ans = 1
 
    for i in range(len(a)):
 
        ans *= a[i]
 
        if ans > 20:
 
            return False
 
    return ans == 20
 
dels = count_del(20)
 
primes = [i for i in range(2, 100) if prime(i)]
 
#Если одна скобка
 
minim = 2**19
 
#Все остальные случаи
 
for j in range(2, 4):
 
    for i in combinations_with_replacement(dels, j):
 
        if check(i):
 
            t = 1
 
            degrees = i[::-1]
 
            for k in range(len(degrees)):
 
                t = t * (primes[k] ** (degrees[k]-1))
 
            minim = min(minim, t)
 
print(minim)

Показать ответ и решение

Если число имеет разложение вида … , то количество чётных делителей такого числа равно
… (выбрали степень двойки от до , степень каждого простого от до ). По
условию это равно — простое число, как произведение натуральных чисел его можно представить как или
.

Случай : , все число равно , не подходит.

Случай : , какое-то , все остальные — приходим к разложению вида .

На частном случае решение будет выглядеть так:

С помощью стандартной программы найдем подходящие нам числа до для того, чтобы рассмотреть
их:

def dividers(n):
    k = 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if i % 2 == 0:
                k += 1
            if (n // i) % 2 == 0 and n // i != i:
                k += 1
    return k

for i in range(1, 100000):
    if dividers(i) == 7:
        print(i)

Подходящие нам числа в диапазоне до — это , и . Хочется разложить эти
числа:

Заметим, что все числа раскладываются на , где — простое число.

Воспользуемся выведенной формулой для решения:

def prime(x):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

ans = 0
for i in range(int((33333333 // 2)**(1/6)), int((99999999 // 2)**(1/6)) + 1):
    if prime(i):
        if 33333333 <= 2*(i**6) <= 99999999:
            ans += 1
print(ans)

Показать ответ и решение

def is_prime(n):
    if n <= 1:
        return False
    for j in range(2, int(n ** 0.5) + 1):
        if n % j == 0:
            return False
    return True

ans = 0
for j in range(3, 10000):
    if is_prime(j):
        for i in range(26):
            if 33222555 <= 2**i*j**2 <= 99888999:
                ans += 1
print(ans)

Найдите все натуральные числа, принадлежащие отрезку [22 222 222; 88 888 888], у которых ровно различных
делителей. В ответе укажите количество данных чисел.

Показать ответ и решение

def prime(x):
 
    for i in range(2, int(x**0.5)+1):
 
        if x % i == 0:
 
            return False
 
    return True
 

 ans = 0
 
for i in range(int(22222222**0.25), int((88888888+1)**0.25)+1):
 
    if prime(i):
 
        ans += 1
 
print(ans)

Рассматривается множество целых чисел, принадлежащих числовому отрезку [854321; 1087654]. Найдите числа,
нетривиальные делители которых образуют арифметическую прогрессию с разностью d = 10 (чисел > 1). В ответе для
каждого такого числа (в порядке возрастания) запишите сначала само число, а потом – его минимальный нетривиальный
делитель.

Показать ответ и решение

def divs(n):
 
    a = []
 
    for i in range(2, int(n**0.5)+1):
 
        if n % i == 0:
 
            a.append(i)
 
            if i != n//i:
 
                a.append(n//i)
 
    a.sort()
 
    if len(a)>1:
 
        for i in range(len(a)-1):
 
            if a[i]+10 != a[i+1]:
 
                return False
 
    return a
 

 
 for i in range(854321, 1087654+1):
 
    x = divs(i)
 
    if x != False and len(x) > 1:
 
        print(i, x[0])
 

Ответ:

887339 937

944759 967

1028171 1009

1052651 1021

Показать ответ и решение

def count_del(x):
    ans = []
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            if len(str(i)) == 2:
                ans += [i]
            if i != x // i:
                if len(str(x // i)) == 2:
                    ans += [x // i]
    return sorted(ans)


ans = 0
for i in range(333555, 777999 + 1):
    if len(count_del(i)) == 38:
        print(i, count_del(i)[0], count_del(i)[-1])

Ответ:

360360 10 99 776160 10 99

Среди целых чисел, принадлежащих числовому отрезку [398790; 863777], найдите числа, сумма натуральных делителей
которых больше 2700000. Для каждого найденного числа запишите количество делителей и их сумму. В качестве делителей
не рассматривать числа 1 и исследуемое число. Так, например, для числа 8 учитываются только делители 2 и 4. Поиск
ведется от меньших чисел к большим.

Показать ответ и решение

def count_del(x):
 
    ans = []
 
    for i in range(2, int(x**0.5)+1):
 
        if x % i == 0:
 
            ans += [i]
 
            if i != x//i:
 
                ans += [x//i]
 
    return ans
 

 ans = 0
 
for i in range(398790, 863777+1):
 
    if sum(count_del(i)) > 2700000:
 
        print(len(count_del(i)), sum(count_del(i)))

Ответ:

238 2858639

214 2799215

190 2734919

198 2739119

Число называется избыточным, если оно строго меньше суммы своих собственных делителей (то есть всех
положительных делителей, отличных от самого числа). Определите количество избыточных чисел из диапазона [5;
50000].

Показать ответ и решение

def count_del(x):
 
    ans = [1]
 
    for i in range(2, int(x**0.5)+1):
 
        if x % i == 0:
 
            ans += [i]
 
            if i != x//i:
 
                ans += [x//i]
 
    return sum(ans) > x
 

 ans = 0
 
for i in range(5, 50000+1):
 
    if count_del(i):
 
        ans += 1
 
print(ans)

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

Примечание. Нетривиальный делитель — делитель, не равный единице и самому числу.

Показать ответ и решение

def count_del(x):
    ans = 0
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            ans += 1
            if i != x // i:
                ans += 1
        if ans >= 3:
            return True
    return False


ans = 0
for i in range(3, 30000 + 1):
    if count_del(i):
        ans += 1
print(ans)