P2303 [SDOI2012] Longge 的问题

题目描述

现在问题来了：给定一个整数 n，你需要求出
\sum\limits_{i=1}^n \gcd(i, n)
1\leq n< 2^{32}

Solution

显然 \forall x \ \ \ \gcd(x,n) 必定是 n 的约数，所以我们改为枚举 n 的约数

考虑枚举约数 i ，那么我们就要计算 \sum_{i=1}^{\frac{n}{i}}[\gcd(i,\frac{n}{i})=1]

根据欧拉函数定义我们可知 \sum_{i=1}^{\frac{n}{i}}[\gcd(i,\frac{n}{i})=1]=\phi(\frac{n}{i})

所以有
\sum\limits_{i=1}^n \gcd(i, n)=\sum_{d|n}\phi(\frac{n}{d})d

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200010;
int vis[N];   //记录是否被筛；或者用于记录最小质因子
int prime[N]; //记录质数
ll phi[N];   //记录欧拉函数
int sum[N];   //计算欧拉函数的和
ll euler(ll n)  {  
    ll ans=n;  
    for(ll i=2;i*i<=n;i++){  
        if(n%i==0){  
            ans-=ans/i;  
            while(n%i==0){  
                n/=i;  
            }  
        }  
    }  
    if(n>1)ans-=ans/n;  
    return ans;  
}
int main(){
    ll n;
    scanf("%lld",&n);
    long long ans = 0 ;
    for(ll i=1;i*i<=n;++i){
        if(n%i==0){
            ans += 1ll*i*euler(n/i);
            if(i*i!=n){
                ll q = n/i;
                ans += 1ll*q*euler(i);          
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}