Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:试试这份代码

Posted by zhjou at 2014-06-13 18:26:47 on Problem 2429
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator