首页 > itarticle > 【bzoj4804】 Solution Code

【bzoj4804】 Solution Code

admin 12月 02, 2020 0

给定数字$n$（$nle 10^7$)，求：
$$
sum{i=1}^nsum{j=1}^nvarphi(gcd(i,j))
$$
多组数据输入，数据组数$Tle5000$。

Solution

　　简单的一题，直接推导：

$$
begin{aligned}
sum_{i=1}^nsum_{j=1}^nvarphi(gcd(i,j))&=sum_{d=1}^nvarphi(d)sum_{i=1}^{lfloor frac n drfloor}sum_{j=1}^{lfloor frac n drfloor}[gcd(i,j)==1]\
&=sum_{d=1}^nvarphi(d)(2*sum_{i=1}^{lfloor frac n drfloor}varphi(i)-1)
end{aligned}
$$

　　发现后面一个括号带下取整，直接求出$varphi$的前缀和，数论根号分块即可。

Code


using namespace std;
typedef long long ll;
const int N=10000001;
bool vis[N];
int p[N],pcnt;
ll phi[N];
void (){
    phi[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i]){
            p[++pcnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=pcnt&&i*p[j]<N;j++){
            int x=i*p[j];
            vis[x]=true;
            if(i%p[j]==0){
                phi[x]=phi[i]*p[j];
                break;
            }
            phi[x]=phi[i]*(p[j]-1);
        }
    }
    for(int i=2;i<N;i++) phi[i]+=phi[i-1];
}
int main(){
    sieve();
    int T,n;
    ll ans;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        ans=0;
        for(int i=1,j;i<=n;i=j+1){
            j=n/(n/i);
            ans+=(2LL*phi[n/i]-1)*(phi[j]-phi[i-1]);
        }
        printf("%lldn",ans);
    }
    return 0;
}