转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
http://poj.org/problem?id=2480
给出N,求∑gcd(i, N) 1<=i <=N.
推导太犀利了。
首先对于每一个N的因子d,如果gcd(m,n)=d,那我们需要找出有多少这样的m,其实这步比较简单就是d*phi(n/d)。
也许会想,为什么不是n/.d个呢,应该有n/d个都是d的倍数,拥有d这个因子。考虑如果与n/d不互质的一个数乘以d,和n的最大公约数必定不是d,那么就会重复计算,欧拉函数的神奇应用。
由于N比较大,也不适合枚举所有因子,也许打出素数表加上快速求eular可以水过。
先要了解eular函数的一个性质。
phi(p^k)=(p-1)*p^(k-1)
考虑如果N=P^k的时候,那么F[N]=p*phi(p^k-1)=k*p^(k-1)+p^k。
利用eular的积性性质
F[N]=F[p1^k1*p2^k2……pi^ki]=∑(ki*pi^(ki-1)+p^ki).
接下来对于N进行因式分解。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define LL long long
#define MOD 1000000007
using namespace std;
int main(){
LL n;
while(scanf("%lld",&n)!=EOF){
LL ans=1;
for(LL i=2;i*i<=n;i++)
if(n%i==0){
LL k=0,p=1;
while(n%i==0){
k++;
p*=i;
n/=i;
}
ans*=k*(p-p/i)+p;
}
if(n>1)
ans*=2*n-1;
printf("%lld\n",ans);
}
return 0;
}
分享到:
相关推荐
北大POJ1321-Chess Problem POJ1321-Chess Problem
poj 2452 Sticks Problem.md
北大POJ3414-Pots 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj的结题报告,里面有一些详细的说明。poj的结题报告,里面有一些详细的说明
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2262-Goldbach's Conjecture 解题报告+AC代码
北大POJ2388-Who's in the Middle 解题报告+AC代码
poj3045的源码,很久以前写的,语言是C++
在进行ACM编程训练时做字符串专题的一些题目(POJ1782,POJ1790,POJ1951,POJ2003,POJ2121)
北大POJ2488-A Knight's Journey 解题报告+AC代码
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
POJ2528-Mayor's posters 测试数据。数据来源:Alberta Collegiate Programming Contest 2003.10.18 – 问题G
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj-2528 Mayor's posters 测试数据及答案
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告