74. DIVSUM - Divisor Summation

Given a natural number n (1 ≤ n ≤ 500000), please output the summation of all its proper divisors.

Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.

e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

Input. An integer stating the number of test cases (equal to about 200000), and that many lines follow, each containing one integer between 1 and 500000 inclusive.

Output. One integer each line: the divisor summation of the integer given respectively.

Sample Input

3

2

10

20

Sample Output

1

8

22

РЕШЕНИЕ

разложение на множители

Анализ алгоритма

Перебираем все множители i числа n от 1 до . Для каждого делителя i < n суммируем значения i и n / i. Отдельно обрабатываем случай, когда n является полным квадратом. Собственный делитель n не учитываем.

Если n = , то сумма всех делителей числа n (включая собственный делитель n) равна

σ(n) =

Указанную сумму можно записать также в виде

σ(n) = = =

Реализация алгоритма

#include <stdio.h>

int tests, i, n, s;

int main(void)

{

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

s = 0;

for(i = 1; i * i < n; i++)

if(n % i == 0) s += i + n / i;

if(i * i == n) s += i;

s -= n;

printf("%d\n",s);

}

return 0;

}

Реализация с запоминанием

#include <stdio.h>

#include <math.h>

#define MAX 500001

int tests, i, j, sq, n;

int sum[MAX+1];

int main(void)

{

sum[1] = -1;

sq = (int)sqrt(1.0*MAX);

for(i = 2; i <= sq; i++)

for(j = i + i; j < MAX; j += i)

{

sum[j] += i; // i - делитель числа j

if (j / i > sq) sum[j] += j / i;

}

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

printf("%d\n",sum[n] + 1);

}

return 0;

}

Реализация с использованием формулы

#include <stdio.h>

int tests, i, n, nn, p, res;

int main(void)

{

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

res = 1; nn = n;

for (i = 2; i * i <= n; i++)

{

p = i;

while (n % i == 0)

{

n /= i;

p *= i;

}

res *= (p - 1) / (i - 1);

}

if (n > 1) res *= (1 + n);

res -= nn;

printf("%d\n",res);

}

return 0;

}