首页 > 代码库 > BZOJ 2705 SDOI2012 Longge的问题 因数分解+欧拉函数
BZOJ 2705 SDOI2012 Longge的问题 因数分解+欧拉函数
题目大意:给定n,求Σgcd(i,n) (1<=i<=n)
n<=2^32
记fi为n的因数,则Σgcd(i,n)=Σphi(n/fi)*fi
记住分解因数和分解质数时都要用O(√n)的方法 不然准T
然后2^32-1不是质数 找质数验证的时候试试2147483647吧
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 10010 using namespace std; typedef long long ll; ll n,ans; ll f[M]; void Get_Factor(ll x) { ll i; for(i=1;i*i<x;i++) if(x%i==0) f[++f[0]]=i,f[++f[0]]=x/i; if(i*i==x) f[++f[0]]=i; } ll Phi(ll x) { ll i,re=x; for(i=2;i*i<=x;i++) if(x%i==0) { re/=i; re*=i-1; while(x%i==0) x/=i; } if(x!=1) re/=x,re*=(x-1); return re; } int main() { int i; cin>>n; Get_Factor(n); for(i=1;i<=f[0];i++) ans+=Phi(n/f[i])*f[i]; cout<<ans<<endl; }
BZOJ 2705 SDOI2012 Longge的问题 因数分解+欧拉函数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。