Given n and phi(n). Also n <= 1018. You need to factorize n into its canonical prime representation.
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.
n = p * p.
You can check this case easily where n is a square or not.
n = p * q
phi(n) = (p - 1) * (q - 1).
Solving these two equations, we can get values of p and q.
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
 of [A Surya Kiran]. For the storing in long double trick, check this
Tester’s solution: Will be added later.