Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:试试这份代码In Reply To:这题。。。即使是ac程序这组数据也是算不出来的。。。 Posted by:zhanggt1994 at 2014-02-03 23:46:28 #include <cstdlib> #include <iostream> #include <cmath> #include <ctime> #include <algorithm> #define LL long long #define T 11 using namespace std; LL mini,key,a,b,gd,lm,ra,rb,jl[502],fac[650]; int Num[65],Len,ct; LL gcd(LL a,LL b){return b?gcd(b,a%b):a;} LL mul(LL a,LL b,LL m){ LL ans=0; while(b){ if(b&1) ans+=a, ans=ans>=m?ans-m:ans; a<<=1; a=a>=m?a-m:a; b>>=1; } return ans; } LL quick_mod(LL a,LL b,LL m){ LL ans=1;a%=m; while(b){ if(b&1) ans=mul(ans,a,m); a=mul(a,a,m); b>>=1; } return ans; } bool witness(LL a,LL n){ LL t=n-1; int j=0; while((t&1)==0){ j++; t>>=1; } LL x=quick_mod(a,t,n); if(x==1||x==n-1) return false; while(j--){ x=mul(x,x,n); if(x==n-1)return false; } return true; } bool miller_robin(LL n){ if(n<2) return false; if(n==2) return true; if(!(n&1))return false; for(int i=0;i<T;i++){ LL a=rand()%(n-1)+1; if(witness(a,n))return false; } return true; } LL pollard_rho(LL n,int c){ LL x,y,d,p,i=1,k=2; x=rand()%n; y=x; while(1){ i++; x=(mul(x,x,n)+c)%n; if(y==x)return n; if(y>x)p=y-x; else p=x-y; d=gcd(p,n); if(1!=d&&d!=n) return d; if(y==x) return n; if(i==k){ y=x; k<<=1; } } } void find(LL n){ if(n==1) return; if(miller_robin(n)){ jl[ct++]=n; return; } LL p=n; while(p>=n) p=pollard_rho(p,rand()%(n-1)+1); find(p); find(n/p); } void dfs(int cur,LL v){ LL s=1; if(cur>Len){ a=v; b=key/v; if(gcd(a,b)==1){ a*=gd;b*=gd; if(a+b<mini){ mini=a+b; ra=a<b?a:b; rb=a>b?a:b; } } return; } for(int i=0;i<=Num[cur];i++){ if(v*s>=mini) return; dfs(cur+1,v*s); s*=fac[cur]; } } void solve(LL n){ ct=0; find(n); sort(jl,jl+ct); Len=0; memset(Num,0,sizeof(Num)); Num[0]=1; fac[0]=jl[0]; for(int i=1;i<ct;i++){ if(fac[Len]!=jl[i]) fac[++Len]=jl[i]; Num[Len]++; } dfs(0,1); } int main(int argc, char *argv[]) { while(cin>>gd>>lm){ if(gd==lm){ cout<<gd<<" "<<lm<<endl; } else{ mini=lm; key=lm/gd; solve(key); cout<<ra<<" "<<rb<<endl; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator