摘要
Title: 873. 欧拉函数
Tag: 欧拉函数
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

873. 欧拉函数

• 题意

  给定 n 个正整数 ai，请你求出每个数的欧拉函数。

• 思路

  定理：1 ~ n 中a的倍数有 $\frac{n}{a}$ 个

  ---

  ps: 利用容斥原理证明
  

  根据公式求即可，即在求质因子时求

  求一个数的欧拉函数：复杂度$O(sqrt(n))$

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-10 19:33:19
  FilePath: \ACM\Acwing\873.py
  LastEditTime: 2022-03-10 19:49:19
  '''
  
  for _ in range(int(input())):
      n = int(input())
      i = 2
      res = n
      while i <= n // i:
          if n % i == 0:
              res = res * (i - 1) // i
              while n % i == 0:
                  n //= i
          i += 1
      if n > 1:
          res = res * (n - 1) // n
      print(res)