Description
作为体育委员,C君负责这次运动会仪仗队的训练。
仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。
现在,C君希望你告诉他队伍整齐时能看到的学生人数。
Input
共一个数N。
Output
共一个数,即C君应看到的学生人数。
Sample Input
4
Sample Output
9
HINT
【数据规模和约定】对于 100% 的数据,1 ≤ N ≤ 40000
题解Here!
把样例画出来,我们发现,其实题目要求的就是:$sum_{i=1}^nsum_{j=1}^n[gcd(i,j)==1]$
但是这个人站在$(1,1)$啊,怎么办?
整体向右移一位,向上移一位,于是变成了:$sum_{i=1}^{n-1}sum_{j=1}^{n-1}[gcd(i,j)==1]$
然后再加上少算的两个:$(0,1),(1,0)$。
至于那个怎么求,丢给了莫比乌斯反演。
莫比乌斯反演不会看这里:莫比乌斯反演。
注:要特判$n==1$,答案为$0$。
附代码:
#include<iostream> #include<algorithm> #include<cstdio> #define MAXN 50010 using namespace std; int n; int k=0,prime[MAXN],mu[MAXN],sum[MAXN]; bool np[MAXN]; inline int read(){ int date=0,w=1;char c=0; while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();} return date*w; } void make(){ int m=MAXN-10; mu[1]=1; for(int i=2;i<=m;i++){ if(!np[i]){ mu[i]=-1; prime[++k]=i; } for(int j=1;j<=k&&prime[j]*i<=m;j++){ np[prime[j]*i]=true; if(i%prime[j]==0)break; mu[prime[j]*i]=-mu[i]; } } for(int i=1;i<=m;i++)sum[i]=sum[i-1]+mu[i]; } long long solve(int n,int m,int d){ long long ans=0; if(n>m)swap(n,m); n/=d;m/=d; for(int i=1,last=1;i<=n;i=last+1){ last=min(n/(n/i),m/(m/i)); ans+=(long long)(sum[last]-sum[i-1])*(n/i)*(m/i); } return ans; } void work(){ n=read(); if(n==1)printf("0 "); else printf("%lld ",solve(n-1,n-1,1)+2); } int main(){ make(); work(); return 0; }