poj2429 GCD & LCM Inverse 数论 大数分解以及找所有因子
Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 7146 Accepted: 1303

#include <cstdio>#include <cstring>#include <cstdlib>#include <map>#include <algorithm>using namespace std;typedef __int64 ll;ll gcd(ll a,ll b){return (b==0)?a:gcd(b,a%b);}ll Mulmod(ll a,ll b,ll n){ ll exp = a%n, res = 0; while(b) { if(b&1) { res += exp; if(res>n) res -= n; } exp <<= 1; if(exp>n) exp -= n; b>>=1; } return res;}ll exp_mod(ll a,ll b,ll c){ll k = 1;while(b){if(b&1)k = Mulmod(k,a,c);a = Mulmod(a,a,c);b>>=1;}return k;}bool Miller_Rabbin(ll n, ll times){ if(n==2)return 1; if(n<2||!(n&1))return 0; ll a, u=n-1, x, y; int t=0; while(u%2==0){ t++; u/=2; } srand(100); for(int i=0;i<times;i++) { a = rand() % (n-1) + 1; x = exp_mod(a, u, n); for(int j=0;j<t;j++) { y = Mulmod(x, x, n); if ( y == 1 && x != 1 && x != n-1 ) return false; //must not x = y; } if( y!=1) return false; } return true;}ll Pollard_Rho(ll n,ll c){ll x,y,d,i=1,k=2;y = x = rand() % (n-1) + 1;while(1){i++;x = (Mulmod(x,x,n) + c)%n;d = gcd((x-y+n)%n,n);if(d>1&&d<n)return d;if(x==y)return n;if(i==k){k<<=1;y = x;}}}ll factor[200],cnt;void Find_factor(ll n,ll c){if(n==1)return;if(Miller_Rabbin(n,6)){factor[cnt++] = n;return;}ll p = n;ll k = c;while(p>=n)p = Pollard_Rho(p,c--);Find_factor(p,k);Find_factor(n/p,k);}ll fac[1000];int s;ll p,q,nn;void dfs(ll count,int step){ if(step==s) { if(count+nn/count<p) { p=count+nn/count; q=count; } return ; } ll sum; sum=fac[step]; dfs(count*sum,step+1); dfs(count,step+1);}int main(){ll m,n;while(scanf("%I64d%I64d",&m,&n)!=EOF){cnt = 0;n/=m;nn=n;Find_factor(n,120);sort(factor,factor+cnt);s=0;fac[0]=factor[0];for(int i=1;i<cnt;i++){ if(factor[i]!=factor[i-1]) {s++;fac[s]=factor[i];} else fac[s]*=factor[i];}p=1000000000000000000LL;//本来放在外面定义，脑残了dfs(1,0);ll ww=nn/q;if(q>ww) swap(q,ww);printf("%I64d %I64d\n",m*q,m*ww);}}