Problem link
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
Tester’s solution: Will be added later.