[Acwing] 873. 欧拉函数 容斥原理

前言

传送门 : https://www.acwing.com/problem/content/875/ 真简单啊 嘻嘻

思路

欧拉函数 : 求 ( 1 − N ) 中 和 N 互 质 的 数 的 个 数 (1-N)中 和 N 互质的数的个数 (1−N)中和N互质的数的个数 公式如下 : ϕ ( N ) = N × p 1 − 1 p 1 × p 2 − 1 p 2 × … × p m − 1 p m \phi(N)=N \times \frac{p_{1}-1}{p_{1}} \times \frac{p_{2}-1}{p_{2}} \times \ldots \times \frac{p_{m}-1}{p_{m}} ϕ(N)=N×p1​p1​−1​×p2​p2​−1​×…×pm​pm​−1​

公式证明 :

1. 对于每一个自然数 我们都刻有拆成 他的质因子倍数的乘积 (算术基本定理)
2. 根据容斥原理我们可以知道,我们所求的答案就是 ( 1 − N ) (1-N) (1−N)这个集合当中 不包括他质因子的倍数的 集合

CODE

/// 对一个数N 求出1~N 中的 互质数的个数
#include 
using namespace std;
int phi(int x)
{
    int res = x;
    for(int i=2; i1) res = res /x *(x-1);
        return res;
}
void solve()
{
    int n;cin>>n;
    cout