bzoj2705Longge的问题

题目链接

题意很简单

$$ans=\sum_{i=1}^{n}gcd(i,n)$$

然后推一下式子，求一下欧拉函数就好了

细节是由于$BZOJ$的评测计时策略，

不能线性筛啊$……$

必须每个数单独筛

一开始线性筛洛谷上过了，$BZ$果断$T$

/**************************************************************

    Problem: 2705

    User: zhangheran

    Language: C++

    Result: Accepted

    Time:28 ms

    Memory:89184 kb

****************************************************************/

#pragma GCC optimize (2)

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int cnt;

int prime[];

int phi[];

bool ins[];

void Euler()

{

    phi[]=;

    for(int i=;i<=;i++){

      if(!ins[i]) prime[++cnt]=i,phi[i]=i-;

      for(int j=;j<=cnt&&i*prime[j]<=;j++){

        ins[i*prime[j]]=true;

        if(i%prime[j]==){phi[i*prime[j]]=phi[i]*prime[j];break;}

        else phi[i*prime[j]]=phi[i]*(prime[j]-);

        }

    }

    return ;

}

long long getphi(long long n)

{

//  if(n<10000000) return phi[n];

    long long res=n;

    for(long long i=;i*i<=n;i++){

        if(n%i==) res=res/i*(i-);

        while(n%i==) n/=i;

    }

    if(n>) res=res/n*(n-);

    return res;

}

long long x;

long long ans;

int main()

{

//  freopen("1.in","r",stdin);

//  freopen("1.out","w",stdout);

    scanf("%lld",&x);

//  Euler();

    long long i=;

    for(;i*i<x;i++) if(x%i==) ans+=i*getphi(x/i)+(x/i)*getphi(i);

    if(i*i==x) ans+=i*getphi(i);

    printf("%lld",ans);

}

//