2705: [SDOI2012]Longge的问题
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 2554 Solved: 1566
[Submit][Status][Discuss]
Description
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。
Input
一个整数，为N。
Output
一个整数，为所求的答案。
Sample Input
6
Sample Output
15
HINT
【数据范围】
对于60%的数据，0<N<=2^16。
对于100%的数据，0<N<=2^32。
Source
分析：
继续学数学...如果今天不GG，预计应该是高产的一天...然而题目难度2333...
根据Dirichlet卷积：id(i)=i,id=φ×1,(f×g)=Σ(d|n)f(d)*g(n/d)
Σ(1<=i<=n) gcd(i,n)
=Σ(1<=i<=n) id(gcd(i,n))
=Σ(1<=i<=n) Σ(d|gcd(i,n))φ(d)
=Σ(d|n)φ(d)*n/d
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
//by NeighThorn
#define int long long
using namespace std;
//大鹏一日同风起，扶摇直上九万里 int n,m,ans; inline int phi(int x){
int cnt=x;
for(int i=;i<=m;i++)
if(x%i==){
cnt=cnt/i*(i-);
while(x%i==)
x/=i;
}
if(x>)
cnt=cnt/x*(x-);
return cnt;
} signed main(void){
scanf("%lld",&n);
m=sqrt(n);ans=;
for(int i=;i<=m;i++)
if(n%i==){
ans+=phi(i)*n/i;
if(n/i>m)
ans+=phi(n/i)*i;
}
printf("%lld\n",ans);
return ;
}
by NeighThorn