PROBLEM LINK: Rick in Space

AUTHOR: panik


PREREQUISITES: Maths, Totient function


Let’s denote the totient function as T ( N ). So as we know totient function tells
us the count of no.s less than N which are coprime with N. Lets not get in to
the proof of that as it is easily available on the internet. Now what we need to find
out in the question is the count of no.s having GCD with N = d for all possible d,
where d is the divisor of N, as GCD won’t give any other output apart from this.
For a specific GCD count of no.s giving such GCD will be d * T ( N/d )

Therefore the sum of GCD for all no.s less than equal to N is sum ( d * T ( N / d) )
This can also be converted to N/d * T ( d ) ( let N/d = x, now even x is also a
divisor, and hence we can convert it to this form)
Now just try to understand the above proof to find the sum of GCD( x ,N ) for x
from 1 to N.

In the proof, p denotes prime no. and n denotes the power of prime no. in N.
Once you understand the core logic the only thing left to find out is the prime
factors and their frequency in N. Now this step requires some optimizations
due to the given constraints. For this we use a very famous trick sieves of

Using this we pre-calculate all the prime no. upto 10^6. Now the question
arises that if N contains a prime no. greater than 10^6. For this, you need to
understand that N can contain at most 1 prime no. greater than 10^6 and that
with a power of 1 at max. Because if it contains more than 1 prime no. greater
than 10^6, it would exceed the given constraints. Using this we find the prime
factors and their powers in N. A no. <10^12 can have at most 12/13 distinct
prime factors as it roots, so the answer to the question using the above-derived formula will only take O( distinct divisors ) in implementation which is
practically just a constant time.

To read more about totient function :

Expected solution: here

The explanation is really good . I just don’t get how we can go from the first line to the second line in the figure you have posted, i.e from the sum part to the product of sum part. Can you explain that please ?

I will try to explain it,
Note : phi[a* b] = phi[a] * phi[b] * x / phi[x] , where x = gcd (a,b )
if( x== 1) : phi[a* b] = phi[a]* phi[b]

Keeping this in mind, let the prime factorization of N = p1^a p2^b ( lets take only two factors for simplicity, p1 and p2 are primes factors ) , all factors of n can be represented as produc of these prime factors raise to some power,

let d be a factor, then d= p1^x * p2^y , where x = ( 0,1, … ,a) and y =(0,1,… , b)

1 Like