「BZOJ2705」[SDOI2012] Longge的问题
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。
题解
题目中要求出∑gcd(i,N)(1<=i<=N)。
枚举n的约数k，令s(k)为满足gcd(m,n)=k,(1<=m<=n)m的个数，则ans=sigma(k*s(k)) (k为n的约数）
因为gcd(m,n)=k,所以gcd(m/k,n/k)=1,于是s(k)=euler(n/k)
phi可以在根号的时间内求出
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<iostream> #include<cstdio> #include<cmath> #define ll long long using namespace std; ll n,ans; int m; ll phi(ll x) { ll t=x; for(ll i=2;i<=m;i++) if(x%i==0) { t=t/i*(i-1); while(x%i==0)x/=i; } if(x>1)t=t/x*(x-1); return t; } int main() { scanf("%lld",&n); m=sqrt(n); for(int i=1;i<=m;i++) if(n%i==0) { ans+=(ll)i*phi(n/i); if(i*i<n)ans+=(ll)(n/i)*phi(i); } printf("%lld",ans); return 0; } |
Subscribe