PROBLEM LINK: Rick in Space
AUTHOR: panik
DIFFICULTY: Medium
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
Eratosthenes.
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
