### Problem link

### Difficulty

Hard

### Pre-requisites

Number theory

### Problem

Given n and phi(n). Also n <= 10^{18}. 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.