×

Hard

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 code of A Surya Kiran. For the storing in long double trick, check this code of Akshay Aggarwal

Tester's solution: Will be added later.

2.5k53136170
accept rate: 20%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,630
×1,341
×631
×6
×2
×1

question asked: 22 Jan '15, 19:21

question was seen: 1,124 times

last updated: 08 Mar '15, 12:30