Сумма делителей — 2

Задача

Профессор из тридевятого царства решил, что посчитать сумму делителей числа $n$ до $10^{10}$ сможет любой троечник, поэтому усложнил для Кости задачу, дав числа с большим количеством цифр. Но наш герой не хотел сдаваться, уж больно он хотел стать отличником.
Костя очень просит Вас помочь ему в этом деле, ведь он помнит, как успешно Вы справились с предыдущей задачей.

Входные данные

Одно целое число $n \left(1 \leqslant n < 10^{15}\right).$

Выходные данные

Выведите сумму делителей числа $n.$

Тесты

Входные данные Выходные данные
$100000000000031$ $100000000000032$
$10000019$ $10000020$
$400001520001444$ $700002730002667$
$9$ $13$
$304250263527210$ $1281001468723200$
$94083986096100$ $457766517350961$
$1234567898765$ $1517681442816$
$100000000000000$ $249992370597277$
$562949953421312$ $1125899906842623$
$81795$ $161280$
$9999999999999$ $14903272088640$
$997$ $998$
$1325$ $1674$
$2468013$ $3290688$
$951641320$ $2447078400$
$71675429738641$ $71695352830464$
$1100000000033$ $1200000000048$
$6300088$ $11859480$
$98$ $171$
$9102837465$ $15799834440$

Код программы

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

Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$
Для того, чтобы не вычислять $p_k^{\alpha_k+1}$, перепишем данную формулу в следующем виде:
$$\sigma\left(n\right) = \left(\frac{p_1^{\alpha_1}-1}{p_1-1}+p_1^{\alpha_1}\right)\cdot\left(\frac{p_2^{\alpha_2}-1}{p_2-1}+p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(\frac{p_k^{\alpha_k}-1}{p_k-1}+p_k^{\alpha_k}\right).$$

Ссылки

Код решения

Сумма делителей

Задача

Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу:
Найти сумму делителей данного числа $n.$
Костя обратился к Вам как к опытному программисту, который знает алгебру, с просьбой о помощи решить данную задачу.

Входные данные

Одно целое число $n \left(1 \leqslant n < 10^{10}\right).$

Выходные данные

Выведите сумму делителей числа $n.$

Тесты

Входные данные Выходные данные
$12$ $28$
$239$ $240$
$1234$ $1854$
$6$ $12$
$1000000007$ $1000000008$
$44100$ $160797$
$223092870$ $836075520$
$2147483648$ $4294967295$
$678906$ $1471002$
$1111111$ $1116000$
$9876543210$ $27278469036$
$99460729$ $99470703$
$5988$ $14000$
$1$ $1$
$1348781387$ $1617960960$
$135792$ $406224$
$5402250$ $17041284$
$375844500$ $1259767236$
$1000000000$ $2497558338$
$2357947691$ $2593742460$

Код программы

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

Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$

Ссылки

Код решения

e-olymp 442. Построения

Задача

Построение
Иван Петрович преподает в школе физкультуру, но интересуется также математикой, в основном, с практической точки зрения. Например, его интересует вопрос, сколько различных построений существует для группы из [latex]N[/latex] человек. Иван Петрович выяснил, что если [latex]N[/latex]– простое число, то получается только [latex]2[/latex] построения: в колонну по одному ([latex]1[/latex]×[latex]N[/latex]) и в шеренгу ([latex]N×1[/latex]). Эти тривиальные построения возможны для любого [latex]N[/latex]  > [latex]1[/latex] (для [latex]N = 1[/latex] существует только одно построение ([latex]1×1[/latex]), которое не является ни шеренгой, ни колонной). Если [latex]N[/latex] – составное число, то существует и другие нетривиальные построения. Для [latex]100[/latex] человек существует девять построений: ([latex]1×100[/latex]), ([latex]2×50[/latex]), ([latex]4×25[/latex]), ([latex]5×20[/latex]), ([latex]10×10[/latex]), ([latex]20×5[/latex]), ([latex]25×4[/latex]), ([latex]50×2[/latex]) и ([latex]100×1[/latex]).

Входные данные

В первой строке ввода содержится одно целое число [latex]N[/latex] (1  ≤[latex]N[/latex]≤  109).

Выходные данные

Вывести одно целое число – количество различных построений для группы из [latex]N[/latex] человек.

Тесты

# Входные данные Выходные данные
1 100 9
2 1 1
3 6 4
4 999983 2
5 2 2

Код программы

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

По условию задачи требуется найти все возможные построения. Это значит, что мы должны найти все возможные варианты разбиения числа на множители. Для этого можно обойтись перебором всех делителей числа от 1 до корня из этого числа, а затем умножить полученное значение на 2 так как для нас имеет значение порядок делителей. Если корень из числа есть делитель данного числа то увеличиваем счетчик на 1.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

A324. Делители одного числа, взаимно простые с другим

Задача

Даны целые числа [latex]p[/latex] и [latex]q[/latex]. Получить все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex].

Тесты

[latex]q[/latex] [latex]p[/latex] Все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex]
40 15 1 2 4 8
87 3 1 29

Код программы

Код программы на С++

Код программы на Java

Решение

Воспользуемся рекурсивной реализацией алгоритма Евклида. Пусть [latex]m[/latex] и [latex]n[/latex] — не равные нулю целые неотрицательные числа, и пусть [latex]m\geq n[/latex]. Тогда, если [latex]n=0[/latex], [latex]GCD(n,m)=m[/latex], а если [latex]n\neq 0[/latex], то для числе [latex]m[/latex], [latex]n[/latex] и [latex]k[/latex], где [latex]k[/latex] — остаток от деления [latex]m[/latex] и [latex]n[/latex], выполняется равенство [latex]GCD(m,n)=GCD(n,k)[/latex].
Для нахождения делителей числа [latex]q[/latex] взаимно простых с [latex]p[/latex], программа проверяет остатки от деления [latex]q[/latex] на все числа [latex]i[/latex] от [latex]1[/latex] до [latex]q[/latex]. Если остаток равен нулю, то число [latex]i[/latex] является делителем [latex]q[/latex]. Для каждого такого числа выполняется поиск наибольшего общего делителя (НОД — Greatest common divisor, GCD) [latex]i[/latex] и [latex]p[/latex] по алгоритму Евклида. Если найденный наибольший делитель равен 1, то числа [latex]i[/latex] и [latex]p[/latex] взаимно простые.

Ссылки

Условие задачи
Решение задачи на сайте Ideone.com (C++)
Решение задачи на сайте Ideone.com (Java)

e-olymp 517. Задачка от Николая

Задача на e-olymp

Приближается Новый год! Третьеклассники уже мечтают побывать возле новогодней елки в Киеве. Учительница математики одного из 3-х классов г. Александрия им сообщила, что она сможет свозить на ёлку в Киев только тех учеников, которые решать задачку от святого Николая. Он хочет узнать качество заданного числа.

По мнению Николая, качеством числа [latex]N[/latex] является сумма цифр всех натуральных чисел [latex] A[/latex] не больших самого числа [latex] N[/latex] таких что остаток от деления числа [latex] N[/latex] на число [latex] A[/latex] равен [latex] 0[/latex] .

Входные данные

Первая строка содержит натуральное число [latex]N[/latex] – количество учеников в 3-м классе. В последующих [latex]N[/latex] строках размещены задания для каждого ученика: натуральное число не больше чем [latex] 15 000 000[/latex] (Николай решил пожалеть учеников и числа выбрал не очень большие)

Выходные данные

Для каждого из чисел, заданных Николаем ученикам, укажите его качество.

Код:
Тесты:

Количество строк 1 задание 2 задание Вывод
2 2 10 3; 9
2 2 1500000 3; 666
2 5 9 6; 13
2 60 15000000 42; 978
2 1 0 1; 0

Решение

В данной задаче я выделил отдельную функцию — [latex]SumOfDigit()[/latex]. Не трудно догадаться, что она считает сумму цифр числа для будущих вычислений. Для первого цикла мы сначала должны ввести число [latex]N[/latex] — количество заданий для учеников. Именно столько раз будет выполняться основной цикл. Чтобы определить качество числа, необходимо найти все его натуральные делители. Для решения данной задачи я воспользовался методом перебора всех чисел до корня из исходного, что значительно ускоряет вычисление по сравнению с перебором вплоть до самого числа. Во внутреннем цикле проверяется каждое число, и если оно удовлетворяет условию, то вызывается функция [latex]SumOfDigit[/latex], а в переменную [latex]sum[/latex] записываются значения сумм.

Данная строка необходима для проверки, если исходное число является квадратом.

В конце основного цикла программа печатает на экран качество данного числа.

Данная задача решалась совместно со Стасом Коциевским на факультативе.

Код на ideone.com

Принятое решение на e-olymp