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;
}
0 条评论