3222 - 公约数

4

4

提示

【Hint】

4 对x，y 为（2，2），（2，4），（3，3），（4，2）

对于20%的数据，N<=1000

对于100%的数据，N<=10000000

C++解答

#include<cstdio>
#define LL long long
const int maxn=10000001;
LL n,ans,s[maxn];
bool b[maxn]={0};
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) s[i]=i;
    for(int i=2;i<=n;i++)
	{
		s[i]+=s[i-1];
        if(!b[i]) 
        {
        	s[i]--;
            for(int j=i<<1;j<=n;j+=i) s[j]=(s[j]/i)*(i-1),b[j]=1;
        }
    }
    for(int i=2;i<=n;i++) if(!b[i]) ans+=(s[n/i]<<1)-1;
    printf("%lld",ans);             
}