| ||||||||||
| 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