题目描述
给定n个正整数ai,请你求出每个数的欧拉函数。
欧拉函数的定义
1 ~ N 中与 N 互质的数的个数被称为欧拉函数,记为ϕ(N)。
若在算数基本定理中,N=pa11pa22…pamm,则:
ϕ(N) = N∗p1−1p1∗p2−1p2∗…∗pm−1pm
输入格式
第一行包含整数n。
接下来n行,每行包含一个正整数ai。
输出格式
输出共n行,每行输出一个正整数ai的欧拉函数。
数据范围
1≤n≤100,
1≤ai≤2∗109
样例
输入样例:
3
3
6
8
输出样例:
2
2
4
#include<iostream>
using namespace std;
const int N=1000010;
bool st[N];
int phi[N],primes[N],cnt;
typedef long long LL;
LL geteuler(int n)//用线性筛的思路 筛欧拉函数
{
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++]=i;
phi[i]=i-1;//质数只和自己本身不互质
}
for(int j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0)//详细证明请见图片
{
phi[primes[j]*i]=primes[j]*phi[i];
break;
}
phi[primes[j]*i]=phi[i]*(primes[j]-1);
}
}
LL res=0;
for(int i=1;i<=n;i++) res+=phi[i];
return res;
}
int main()
{
int x;
cin>>x;
cout<<geteuler(x);
}