IITK2P05 - Editorial

Problem link

contest
practice

Difficulty

Hard

Pre-requisites

Number theory

Problem

Given n and phi(n). Also n <= 1018. You need to factorize n into its canonical prime representation.

Solution

Check whether n is prime or not
For that you can simply check the fact whether phi(n) is equal to n - 1 or not.

Remove all factors f <= 10^6
You can simply iterate over f from 1 to 10^6 and check whether n is divisible by f or not. This way you can find all the factors up to 10^6.

Now your n will have a specific form
Now you can notice that your number n will not have any prime factor <= 10^6. So all prime factors will be greater than 10^6. As n <= 10^18, there can be at most primes factors of n.

So n can of following two forms.
Case 1
n = p * p.
You can check this case easily where n is a square or not.

Case 2
n = p * q
phi(n) = (p - 1) * (q - 1).

Solving these two equations, we can get values of p and q.

Small pitfalls
Note that for getting values p and q, you have to do operations in which your intermediates values will exceed long long. For that you can either use big-integer or you can do a small
trick of storing numbers in long double. For the first big-integer solution, check this


[555] of [A Surya Kiran][666]. For the storing in long double trick, check this 

777
of Akshay Aggarwal

Tester’s solution: Will be added later.