题解|题解大数拆分 POJ 2429 题解大数拆分POJ2429

题意：给出两个数的gcd和lcm 求这两个数，要求为这两个数相加是所有满足条件的数的最小的那一对。
做法：关于gcd和lcm有两个基本公式。1.a*b=gcd*lcm 2.a=k1*gcd,b=k2*gcd,c=lcm/gcd,得 k1*k2=c;
由公式2可得。对c进行拆分后所得所有因子，可任意分配给k1和k2.（前提是两个相同的因子不能同时给k1和k2，否则会导致a,b不互质）
代码：

#include #include #include #include #include #include using namespace std; typedef long long int64; int64 gcd(int64 a,int64 b) { return b==0?a:gcd(b,a%b); } int64 mult_mod(int64 a,int64 b,int64 c)//计算a*b%c { int64 ret=0; int64 tmp=a; a%=c,b%=c; //保证a,b小于c，节约计算时间。 while(b) { if(b&1) { ret+=tmp; if(ret>c)ret-=c; } tmp<<=1; if(tmp>c)tmp-=c; b>>=1; } return ret; } int64 pow_mod(int64 a,int64 n,int64 mod)//计算a^n%mod { int64 ret = 1; int64 tmp = a%mod; while(n) { if(n & 1)ret = mult_mod(ret,tmp,mod); tmp = mult_mod(tmp,tmp,mod); n >>= 1; } return ret; } bool check(int64 a,int64 n,int64 x,int64 t)//判断是不是合数 { int64 ret = pow_mod(a,x,n); int64 last = ret; for(int i = 1; i <= t; i++) { ret = mult_mod(ret,ret,n); if(ret == 1 && last != 1 && last != n-1)return true; //合数 last = ret; } if(ret != 1)return true; else return false; } bool Miller_Rabin(long long n,int k)//米勒罗宾（判断是不是素数） { if( n < 2)return false; if( n == 2)return true; if( (n&1) == 0)return false; //偶数 long long x = n - 1; long long t = 0; while( (x&1)==0 ){x >>= 1; t++; } srand(time(NULL)); for(int i=0; i=n) p=pollard_rho(p,c--); //值变化，防止死循环k findfac(p,k); findfac(n/p,k); } int64 mins,aa,bb; int top; void dfs(int64 a,int64 b,int p)//将所有质数进行分配 { if(a+b>=mins) return; if(p==top) { if(a+b>1; tot=0; c=l/g; findfac(c,107); top=0; sort(factor,factor+tot); for(int i=0; ibb) swap(aa,bb); printf("%I64d %I64d\n",aa,bb); } return 0; }

【题解|题解大数拆分 POJ 2429】转载于:https://www.cnblogs.com/ghh1995/p/4349010.html