1782. The sum of divisors
Let n be a positive integer. A number d is called a divisor of
n if 1 ≤ d ≤ n and n is divisible by d without remainder. Find the sum of all divisors of the number n.
Input. One positive integer n (1 ≤ n
≤ 1018). It is known that all prime divisors of n do not
exceed 1000.
Output. Print the
sum of all divisors of the number n.
|
Sample
input |
Sample
output |
|
239 |
240 |
SOLUTION
number theory
Algorithm analysis
Consider the function σ(n), which maps a positive integer n to the sum of all its
positive divisors.
·
If n = p, where p is a prime number, then n has exactly two divisors: 1 and p. Therefore,
σ(n) = 1 + p
·
If n = pa, where p is a prime number and a ≥ 1, then all divisors of n
are of the form:
1, p, p2,
…, pa
Their sum
forms a geometric progression; therefore,
σ(pa) = 1 + p + p2 + p3 + … + pa = 
The function σ(n) is multiplicative, that is, for any
pair of coprime integers x and y, the following equality holds:
σ(xy) = σ(x) σ(y)
Let a positive integer n have the following
prime factorization
n = 
,
where p1,
p2, …, pk are distinct prime numbers.
Then, using the
multiplicativity of σ(n) and the formula for powers of prime
numbers, we obtain:
σ(n) = σ(
) * σ(
) * … * σ(
) = 
The
above sum can also be written in the following form:
σ(n) = 
= 
= 
Example
The number n = 239 is prime, that is, it has exactly two positive divisors: 1 and 239. By the definition of the sum-of-divisors function, we obtain:
σ(239) = 1 + 239 = 240
Consider the number n = 24. Its prime factorization is:
24 = 23 * 3
Since the numbers 23 and 3 are coprime, we can apply
the multiplicativity of the function σ(n):
σ(24) = σ(23) * σ(3) = (1 + 2 + 4 + 8) * (1 +
3) = 15 * 4 = 60.
Let’s compute the sum of
the divisors of the number n = 24 directly.
First, list all positive divisors of 
:
1, 2, 3, 4, 6,
8, 12, 24
Adding them together, we
obtain:
σ(24) = 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24
Notice that all divisors
can be grouped in the following way:
σ(24) =
1 + 2 + 3 + 4 + 6 + 8 + 12 + 24 =
1 + 2 + 4 + 8 +
3 * (1 + 2 + 4 + 8) =
(1 + 2 + 4 + 8)
* (1 + 3) = 15
* 4 = 60
Algorithm implementation
Read the input value n.
scanf("%lld",&n);
Store the value of σ(n) in the variable res.
res = 1;
Using the variable i, iterate over all prime divisors of the number n (according to the problem
statement, they do not exceed 1000). For each such divisor, compute its contribution to the sum of
divisors of n using the formula derived in the problem analysis.
for (i = 2; i <= 1000; i++)
{
p = i;
Let i be a prime divisor of n. Find the largest exponent a such that ia divides
n.
while(n % i
== 0)
{
n /= i;
p *= i;
}
After the loop terminates, we obtain p = ia+1.
Then we multiply the current value of the variable res by 
.
res *= (p - 1) / (i - 1);
}
Print the answer.
printf("%lld\n",res);
Java implementation
import java.util.*;
class Main
{
public static void main(String[]
args)
{
Scanner con = new Scanner(System.in);
long n =
con.nextLong();
long res = 1;
for(int i = 2; i <=
1000; i++)
{
long p = i;
while(n % i == 0)
{
n /= i;
p *= i;
}
res *= (p - 1) / (i - 1);
}
System.out.println(res);
con.close();
}
}
Python implementation
Read the input value n.
n = int(input())
Store the value of σ(n) in the variable res.
res = 1
Using the variable i, iterate over all prime divisors of the number n (according to the problem
statement, they do not exceed 1000). For each such divisor, compute its contribution to the sum of
divisors of n using the formula derived in the problem analysis.
for i in range (2,1000) :
p = i
Let i be a prime divisor of n. Find the largest exponent a such that ia divides
n.
while(n % i
== 0) :
n = n // i
p *= i
After the loop terminates, we obtain p = ia+1.
Then we multiply the current value of the variable res by .
res *= (p - 1) // (i - 1)
Print the answer.
print(res)