XX86's blog

By XX86, history, 4 weeks 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

»
4 weeks ago, # |
  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
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For x≥3 ϕ(x) is even, and ϕ(x)=1 for x=1 or x=2 but 1 is not a prime number So the only possible prime value for ϕ(x) is 2. oh!yeah.thanks!