1782. The sum of divisors

 

Let n be a positive integer. The number d is its divisor if 1 ≤ d ≤ n and the remainder after dividing n by d is zero. Find the sum of divisors of number n.

 

Input. One integer n (1 ≤ n ≤ 1018), all its prime divisors do not exceed 1000.

 

Output. Print the sum of divisors of number n.

 

Sample input

Sample output

239

240

 

 

SOLUTION

number theory

 

Algorithm analysis

Let σ(n) be the function that computes the sum of all divisors of number n.

·        If n = p (p is prime), then σ(n) = 1 + p;

·        If n = pa (p is prime), then σ(pa) = 1 + p + p2 + p3 + … + pa = ;

Function σ(n) is multiplicative. If n  = , then

σ(n) = σ() * σ() * … * σ() =

This sum can also be written in the form

σ(n) =  =  =

 

Example

n = 239 is prime, σ(239) = 1 + 239 = 240.

n = 24 = 23 * 3, σ(24) = σ(23) * σ(3) = (1 + 2 + 4 + 8) * (1 + 3) = 15 * 4 = 60.

Let’s calculate the sum of divisors for n = 24 directly: σ(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 realization

Read the input value of n.

 

scanf("%lld",&n);

res = 1;

 

In the variable i iterate over all prime divisors of n (according to the problem statement, they are no more than 1000). Calculate the sum of divisors of n using the formula given in the analysis of the problem.

 

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

{

  p = i;

 

Let i be a prime divisor of n. Find the maximum power of a for which ia divides n.

 

  while(n % i == 0)

  {

    n /= i;

    p *= i;

  }

 

After the while loop we have p = ia+1. Multiply res by .

 

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

}

 

Print the answer.

 

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

 

Java realization

 

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 realization

 

n = int(input())

res = 1

for i in range (2,1000) :

  p = i

  while(n % i == 0) :

    n = n // i

    p *= i

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

print(res)