题目描述

新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。

第一行是测试数据的组数CN（Case number，1<CN<10000），接着有CN行正整数N（1<n<32768），表示会员人数。

对于每一个N，输出一行新朋友的人数，这样共有CN行输出。

样例

2
25608
24027

7680
16016

算法

欧拉函数介绍：    

      欧拉函数，在数论中用于求解 [ 1 , n ] 中与 n  互质数个数 的函数，因为研究者为欧拉，故命名为欧拉函数。

      通式：φ(x) = x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。

      φ(1) = 1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如 12 = 2*2*3 那么      φ(12) = 12 * (1-1/2) * (1-1/3)=4  )

      若 n = p^k  (  p为 质数 )，则 φ(n) = p^k-p^(k-1) = (p-1)p^(k-1)，（ 除 p 的倍数外，其他数均为 p 的互质数 ）。

      若n = p（ p 为质数），则  φ(n) = p-p^(1-1) = p-1。

欧拉函数性质：

     1、  φ(mn) = φ(m) φ(n)

     2、若n为奇数，φ(2n) = φ(n)。

    （注意：在欧拉函数中，函数值是 [ 1 , n ] 中与 n  互质数个数 ，证明自行百度）

参考文献

详细请看链接的y总讲解

视频讲解：https://www.acwing.com/video/298/

C++ 代码

#include <iostream>
#include <cmath>
using namespace std;

int phi(int x) {
    int res = x;

    for (int i = 2; i <= x / i; i ++ )

        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }

    if (x > 1) res = res / x * (x - 1);

    return res;
}

int main() {
    int T,N;
    cin >> T;

    while( T-- && cin >> N) {

        cout << phi(N) << endl;

    }

    return 0;
}