数学之神

之神"/>

数学之神

题目大意

求在n（n<=10^7）以内的正整数中与其互质的个数以及这些数的和。

phi

第一问相当于求phi(n),那第二问呢？
注意到如果gcd(n,a)=1,那么gcd(n,n-a)=1，这两个数都与n互质且和为n。
那么只要n不为2，答案就为phi(n)*n/2。
巧合的是n为2也符合这个式子。

优化筛法

我们发现直接筛phi很慢，过不了。
我是蒟蒻不会线性筛，但在考场上想到了这样一个方法通过了所有数据。
我们可以筛出f[i]表示能整除i的最小质数，这个可以在时限内完成。
观察 phi(n)=n∗a1−1a1∗...am−1am $phi(n)=n*\frac{a1-1}{a1}*...\frac{am-1}{am}$
其中a1…am都是能够整除n的不同质数。
我们将 a1−1a1 $\frac{a1-1}{a1}$看作 f[i]−1f[i] $\frac{f[i]-1}{f[i]}$
那么我们想如何得到后面那串。
我们设g[i]表示一个最大的值可以整除i但不能被f[i]整除。
后面那串就是phi[g[i]]/g[i]。
显然如果f[i]=f[i/f[i]]那么g[i]=g[i/f[i]]否则g[i]=i/f[i]。

参考程序

#include<cstdio>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=10000000+10;
bool bz[maxn];
int phi[maxn],f[maxn],g[maxn];
int i,j,k,l,t,n,m,tot;
long long ans,cnt;
int main(){fo(i,2,floor(sqrt(10000000)))if (!f[i]){f[i]=i;fo(j,i,10000000/i)if (!f[i*j]) f[i*j]=i;}phi[1]=1;fo(i,2,10000000){if (!f[i]) f[i]=i;if (f[i]==f[i/f[i]]) g[i]=g[i/f[i]];else g[i]=i/f[i];phi[i]=i/f[i]*(f[i]-1)/g[i]*phi[g[i]];}phi[1]=0;scanf("%d",&t);fo(i,1,t){scanf("%d",&n);cnt=phi[n];if (n==1) ans=0;else if (n==2) ans=1;else ans=cnt*n/2;printf("%lld %lld\n",cnt,ans);}return 0;
}