Bzoj2705 [sdoi2012]longge的问题

Posted by yjjr's blog on February 6, 2018

标签:欧拉函数,数论

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),设x为N的约数

∑gcd(I,N)=∑phi(N/x)*x

求phi的时候要用O(√n)的算法

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define LL long long
#define rep(i,a,b) for(LL i=a;i<=b;i++)
#define dep(i,a,b) for(LL i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
long long n,ans,m;
LL phi(LL x)
{
	LL t=x;
	rep(i,2,m)
	    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()
{
	cin>>n;
	m=sqrt(n);
	rep(i,1,m)
		if(n%i==0){
			ans+=i*phi(n/i);
			if(i*i<n)ans+=(n/i)*phi(i);
			}
	cout<<ans<<endl;
	return 0;
}


本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr