You are not logged in. Please login at www.codechef.com to post your questions!

×

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 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.

asked 22 Jan '15, 19:21

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53136170
accept rate: 20%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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