大数的公约数求解
发布时间:2020-12-14 03:05:35 所属栏目:大数据 来源:网络整理
导读:1. 基本知识 GCD、欧拉定理、因式分解 最方便因式分解 scanf("%d",a);for(j=2;j*j=a;j++){ while(a%j==0) a/=j,A[j]++;}if(a1) A[a]++; 根据欧拉公式,我们可以将任何一个数表示成如下形式: n=p1^x1*p2^x2*p3^x3.......*pm^xm; ? 如果将A和B分别表示成 A =
1. 基本知识 GCD、欧拉定理、因式分解 最方便因式分解 scanf("%d",&a); for(j=2;j*j<=a;j++) { while(a%j==0) a/=j,A[j]++; } if(a>1) A[a]++; 根据欧拉公式,我们可以将任何一个数表示成如下形式: n=p1^x1*p2^x2*p3^x3.......*pm^xm; ? 如果将A和B分别表示成 A = p1^a1 * p2^a2 * … * pn^an B = p1^b1 * p2^b2 * … * pn^bn 其中p1,p2....都是素数,a1,a2...都是整数 那么 GCD( A,B ) = p1^min(a1,b1) * p2^min(a2,b2) * … * pn^min(an,bn)对于这样由N个数乘积组成的数,我们可以将N个数的拆分结果全部保存在同一个A数组中,最终的结果就是超大数自身的拆分。 #include<iostream> #include<string> #include<map> using namespace std; #define mod 1000000000 map<int,int>A,B; int n,m,a; __int64 ans; int min(int a,int b) { return a<b?a:b; } int main() { int i,j; freopen("D:in.txt","r",stdin); while(scanf("%d",&n)==1) { A.clear();B.clear(); for(i=0;i<n;i++) { scanf("%d",&a); for(j=2;j*j<=a;j++) { while(a%j==0) a/=j,A[j]++; } if(a>1) A[a]++; } scanf("%d",&m); for(i=0;i<m;i++) { scanf("%d",B[j]++; } if(a>1) B[a]++; } ans=1; int flag=0; map<int,int>::iterator it; for(it=A.begin();it!=A.end();it++) { if(B.count(it->first)) { int p=it->first; int r=min(A[p],B[p]); for(i=0;i<r;i++) { ans*=p; if(ans>=mod) { ans%=mod; flag=1; } } } } if(flag) printf("%09dn",(int)ans); else printf("%I64dn",ans); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |