Блог пользователя XX86

Number theory--Euler totient function-codechef
Автор XX86, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
  • 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
→ Ответить