XX86's blog

Number theory--Euler totient function-codechef
By XX86, history, 6 years ago, In English

How Can I solve this problem!https://www.codechef.com/problems/COZIE Can anyone explain,please?

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it
  • If $$$A \times B = LCM(A,B)$$$ then $$$A$$$ and $$$B$$$ are coprime, or number of possible $$$B$$$ is $$$\phi(A)$$$ (where $$$\phi(x)$$$ is Euler's totient fuction)
  • For $$$x \ge 3$$$ $$$\phi(x)$$$ is even, and $$$\phi(x) = 1$$$ for $$$x = 1$$$ or $$$x = 2$$$ but $$$1$$$ is not a prime number
  • So the only possible prime value for $$$\phi(x)$$$ is $$$2$$$
  • You should find all values $$$x$$$ for which $$$\phi(x) = 2$$$ and spot them among given $$$N$$$ numbers
→ Reply