首页 > 代码库 > 2014.11.12模拟赛【最大公因数】
2014.11.12模拟赛【最大公因数】
最大公因数(gcd.c/.cpp/.pas)
题目描述
给定正整数n，求。
样例输入
6
样例输出
15
数据范围
对于40%的数据：1<=n<=1000000
对于100%的数据：1<=n<=3*10^12
提示：保证答案不超过10^18
原创题！
……好吧其实最后发现bzoj2705【longge的问题】跟这个一毛一样，但是这个数据更强
不过我真是独立yy出来的
首先，考虑gcd(i,n)==k的i有几个
显然这是等价于gcd(j,n/k)==1的j有几个，其中1<=j<=n/k
看到gcd==1，即j与n/k互质，你想到什么？显然是欧拉函数啊
gcd(j,n/k)==1的j的个数就是phi(n/k)，其中每个gcd(i,n)==k对答案的贡献是k，所以总的答案就是Σphi(n/k)*k,1<=k<=n且n%k==0
显然这个式子等价于Σphi(k)*(n/k),1<=k<=n且n%k==0
那么对n分解质因数，然后枚举它的每个因子取了多少个，算phi(k)*(n/k)就近似O(1)了
总复杂度是O(sqrt(n))
（所以完全可以开到10^15的，只是怕爆了long long要高精太麻烦）
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define mxprime 1500000using namespace std;bool mrk[1500010];LL prime[1000000],a[100];LL n,wrk,ans;int lenp,len;int b[100],now[100];inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}inline void getprime(){ for (int i=2;i<=mxprime;i++) mrk[i]=1; for (int i=2;i<=mxprime;i++) if (mrk[i]) { prime[++lenp]=(LL)i; for(int j=2*i;j<=mxprime;j+=i)mrk[j]=0; }}inline void dfs(int step){ if (step==len+1) { LL sum=1ll,tot=1ll; for (int i=1;i<=len;i++) { for (int j=1;j<=now[i];j++) sum*=a[i],tot*=a[i]; if (now[i])sum=sum/a[i]*(a[i]-1); } ans+=sum*(n/tot); return; } for(int j=0;j<=b[step];j++) { now[step]=j; dfs(step+1); }}int main(){ getprime(); n=wrk=read(); for (int i=1;prime[i]*prime[i]<=wrk;i++) { LL nowp=prime[i]; if (wrk%nowp==0) { a[++len]=nowp; b[len]=1; wrk/=nowp; while (wrk%nowp==0) { b[len]++; wrk/=nowp; } } } if (wrk!=1) { if (wrk==a[len])b[len]++; else { a[++len]=wrk; b[len]=1; } } dfs(1); printf("%lld\n",ans);}
2014.11.12模拟赛【最大公因数】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。