首页 > 代码库 > POJ 2480 (约数+欧拉函数)
POJ 2480 (约数+欧拉函数)
题目链接: http://poj.org/problem?id=2480
题目大意：求Σgcd(i,n)。
解题思路：
如果i与n互质，gcd(i,n)=1，且总和=欧拉函数phi(n)。
如果i与n不互质，那么只要枚举n的全部约数，对于一个约数d，必有gcd(i/d,n/d)互质，这部分的gcd和=d*欧拉函数phi(n/d).
不断累加暴力求解即可。
其实还可以公式化简，不过实在太繁琐了。可以参考金海峰神的解释。
由于要求好多欧拉函数，每次都分解质因数法必然TLE，这里所以采用O(√n)求单个欧拉函数+Hash记录打表的方法。
#include "cstdio"#include "vector"#include "map"using namespace std;#define LL long longvector<LL> divisor(LL n){ vector<LL> res; for(LL i=1;i*i<=n;i++) if(n%i==0) { res.push_back(i); if(i!=n/i) res.push_back(n/i); } return res;}map<LL,LL> prime_factor(LL n){ map<LL,LL> res; for(int i=2;i*i<=n;i++) while(n%i==0) {++res[i];n/=i;} if(n!=1) res[n]=1; return res;}LL eular(LL n){ LL ans=n; for(LL i=2;i*i<=n;i++) { if(n%i==0) { ans-=ans/i; while(n%i==0) n/=i; } } if(n>1) ans-=ans/n; return ans;}int main(){ LL n; map<LL,LL> table; while(scanf("%I64d",&n)!=EOF) { LL ans=0; vector<LL> div=divisor(n); for(int i=0;i<div.size();i++) { LL e; if(!table.count(n/div[i])) {table[n/div[i]]=eular(n/div[i]);e=table[n/div[i]];} else e=table[n/div[i]]; ans+=(div[i]*e); } printf("%I64d\n",ans); }}
| 13626576 | neopenx | 2480 | Accepted | 556K | 360MS | C++ | 1121B | 2014-11-13 19:24:55 |
POJ 2480 (约数+欧拉函数)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。