BZOJ 2705: [SDOI2012]Longge的问题

starli posted @ 2016年3月06日 15:58 in 数学 , 563 阅读

考虑枚举gcd(i,n) =d 那么只要计数有多少个数和N的gcd是d

显然是phi(n/d)个

假设一个数可以表示成$p_{1}^{a1}+p_{2}^{a2}+...$,那么phi的结果就是 $(p_{1}-1)*p_{1}^{a1-1}*(p_{2}-1)*p_{2}^{a2-1}...$每次找到一个约数之后除干净就可以保证每次找到的都是质因数

计算phi是$\sqrt{n}$(枚举约数的复杂度) 枚举公约数$\sqrt{n}$ 时间复杂度$\sqrt{n}$

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
LL n,sq,ans;
LL phi(LL x){
	LL tmp=(LL)sqrt(x),ret=1;
	for(int i=2;i<=tmp;i++){
		if(x%i==0){
			ret*=i-1;x/=i;
			while(x%i==0) x/=i,ret*=i;
		}
	}
	if(x>1)ret=ret*(x-1);
	return ret;
}
int main(){
	scanf("%lld",&n);sq=(LL)sqrt(n);
	for(int i=1;i<=sq;i++){
		if(n%i==0) {
			ans+=i*phi(n/i);
			if(n/i!=i) ans+=(n/i*phi(i));
		}
	}
	printf("%lld",ans);
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter