题解
分解质因数
+埃氏筛法
+容斥原理
欧拉函数ora(N):求1~N中与N互质的数字个数
互质:公约数只有1的两个整数互质
- 求1~N中与N互质的数字个数实际上就是求
1~N中与N没有非1公约数的数字的个数
那我们要先把N分解质因数
$$N=p_1^{k_1}p_2^{k_2}…p_n^{k_n}$$ - 我们先把$p_i$的倍数删掉($-\frac{N}{p_i}$),由于有重叠的部分,比如$p_1*p_2$的倍数就被删掉了两次,所以还要把两个约数相乘的组合都加回来,再减去三个约数相乘的组合…(容斥原理)
$$Num=N-\frac{N}{p_1}-\frac{N}{p_2}-\frac{N}{p_3}+\frac{N}{p_1p_2} +\frac{N}{p_1p_3}+\frac{N}{p_2p_3}-\frac{N}{p_1p_2p_3} $$ -
我们观察会发现,
-
当分母pi的个数为奇数时,前面的符号为负号,反之为正号;
- 分母的排列组合实际上就是
从p1~pn选择任意多个相乘的方案
。
所以我们让不选pi这一项的时候为1,选的时候为-pi:
$$⭐️⭐️⭐️欧拉函数公式:Φ(N)=N\times (1-\frac{1}{p_1} ) \times (1-\frac{1}{p_2}) \times (1-\frac{1}{p_3})$$
即可得到这个一般的公式。
代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
void divide(long N,vector<double> &v){//分解N为质因数->存到v里面
if(N<2) return;
bool flag=false;;
for(long i=2;i<=N/i;i++){
flag=false;
while(N%i==0) N/=i,flag=true;
if(flag) v.emplace_back(i);
}
if(N!=1) v.emplace_back(N);
}
double ora(long N){//求N的欧拉函数
vector<double> v;
divide(N,v);
double product=1;
for(auto x:v){
product*=(1-1/x);
}
product*=N;
return product;
}
int main(void){
long n,N;
double result;
cin>>n;
while(n--){
cin>>N;
result=ora(N);
printf("%.0f\n",result);
}
}