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

Данная задача является упрощенным вариантом задания олимпиады KPI-OPEN 2018.

Задача

Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу:
Найти сумму делителей данного числа $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}.$$

Ссылки

Код решения

А329. Квадрат суммы цифр числа

Задача

Задача из сборника задач по программированию Абрамова С.А. 2000 г.
Даны натуральные числа $n$, $m$. Получить все меньшие натуральные числа, квадрат суммы цифр которых равен $m$.

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

Два положительных числа $n$ и $m$.

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

Все целые числа из $\left ( 0, n \right )$, удовлетворяющие условию.

Тесты

Входные данные Выходные данные
$1234 \ 9$ $3 \ 12 \ 21 \ 30 \ 102 \ 111 \ 120 \ 201 \ 210 \ 300 \ 1002 \ 1011 \ 1020 \ 1101 \ 1110 \ 1200$
$100 \ 4$ $2 \ 11 \ 20$
$49 \ 49$ $7 \ 16 \ 25 \ 34 \ 43$
$1000 \ 1$ $1 \ 10 \ 100$

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

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

Находим сумму цифр каждого числа от $1$ до $n$, проверяя равняется ли эта сумма, возведенная в квадрат, числу $m$. В случае положительного ответа, выводим число, сумму цифр которого мы проверяли.

Ссылки

Условие задачи (страница 135)
Код решения

e-olymp 446. Ровные делители

Задача

Натуральное число $m$ называется ровным делителем числа $n$, если частное и остаток от деления $n$ на $m$ равны. По заданному натуральному числу $n$ найти количество его ровных делителей.

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

Натуральное число $n \space (1 ≤ n ≤ 10^{6})$.

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

Выведите искомое количество ровных делителей числа $n$.

Тесты

Входные данные Выходные данные
5 1
20 2
200 6
653 1
5982 4

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

Решение

Для решения этой задачи сперва введем переменную q , в которой будем хранить количество ровных делителей числа $n$. Затем запустим цикл, который будет проверять каждое из чисел от $1$ до $n$ включительно, является ли оно ровным делителем. Если условие выполняется, то увеличиваем значение, хранящееся в q на единицу. После цикла выведем искомое на экран.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone
Решение этой же задачи на C++

A278

Задача A278

Условие задачи

Даны натуральные числа n_{1},\dots,n_{m}, действительные числа x_{1},\dots,x_{m}. Вычислить \frac{n_{1}\cdot x_{1}+\dots+n_{m}\cdot x_{m}}{n_{1}+\dots+n_{m}}.

Тестирование

Входные данные Выходные данные
1. 1 2 4 -1 -0.4
2. 1 2 3 4 5 0.6 1.88889
3. 5 -2 1 0.2 3 -3 2 0 -1.70909
4. 10 3.3 4 0.4 6 0.01 8 1 1 8 1.7469
5. 3 -0.5 2 -0.4 1 -0.3 5 32 11 5 20 -1 4.58095

 

Код

Алгоритм решения (потоковая обработка)

Считываем числа до конца входного потока и поочередно записываем их в переменные n и n соответственно.
Пока вводятся данные:

  1. Вычисляем значение выражения n_1\cdot x_1+\dots+n_m\cdot x_m, накапливая сумму в числитель n.
  2. Вычисляем значение выражения n_1+\dots+n_m, накапливая сумму  в делителе n.
  3. Находим результат n от деления n на  n

Код на ideone.com