JZOJ 4234 数学之神（phi模板）

题目大意

给出一个n，求phi(n)及2~n-1中与n互质的数的个数。

多组数据，T<=100000,n<=10000000 时间限制 1s 空间限制 256M

解题思路

互质的数个数为phi(n)*n/2

#include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define maxn 10000000+6 #define fr(i,a,b) for(i=a;i<=b;i++) using namespace std; typedef long long ll; int i,j,k,n,T; ll pri[maxn],phi[maxn]; bool kan[maxn]; void pre(ll n) { int tot=0; fr(i,2,n-1) { if (!kan[i]) { pri[++tot]=i; phi[i]=i-1; } fr(j,1,tot) { ll k=i*pri[j]; if (k>n) break; kan[k]=1; if (i%pri[j]==0) { phi[k]=phi[i]*pri[j]; break; } else phi[k]=phi[i]*(pri[j]-1); } } return; } int main() { scanf("%d",&T); pre(10000000); while (T--) { scanf("%d",&n); printf("%lld %lld\n",phi[n],phi[n]*n/2); } return 0; }