1 //Accepted    172 KB    172 ms  2 //该程序为随机性算法，运行时间不定  3 #include <cstdio>  4 #include <cstring>  5 #include <iostream>  6 #include <ctime>  7 #include <algorithm>  8 using namespace std;  9 long long factor[1000],factor_top=-1; 10 //gcd 11 long long gcd(long long a,long long b) 12 { 13     if (b==0) return a; 14     return gcd(b,a%b); 15 } 16 //a*b%n n<2^62 17 long long mult_mod(long long a,long long b,long long n) 18 { 19     long long exp=a%n,res=0; 20     while (b) 21     { 22         if (b&1) 23         { 24             res+=exp; 25             if (res>n) res-=n; 26         } 27         exp<<=1; 28         if (exp>n) exp-=n; 29         b>>=1; 30     } 31     return res; 32 } 33 //return a^b%n 34 long long exp_mod(long long a,long long b,long long n) 35 { 36     long long res=1,exp=a%n; 37     while (b>=1) 38     { 39         if (b&1) 40         { 41             res=mult_mod(res,exp,n); 42         } 43         exp=mult_mod(exp,exp,n); 44         b>>=1; 45     } 46     return res; 47 } 48 //miller_rabin 算法进行素数判定 49 //判断次数times次 一般取times=10 50 //return true 则n为素数 51 bool miller_rabin(long long n,long long times) 52 { 53     if (n==2) return true; 54     if (n<2 || !(n&1)) return false; 55     long long a,u=n-1,x,y; 56     int t=0; 57     while (u%2==0) 58     { 59        t++; 60        u/=2; 61     } 62     srand(time(0)); 63     for (int i=0;i<times;i++) 64     { 65         a=rand()%(n-1)+1; 66         x=exp_mod(a,u,n); 67         for (int j=0;j<t;j++) 68         { 69             y=mult_mod(x,x,n); 70             if (y==1 && x!=1 && x!=n-1) 71             return false; //not prime 72             x=y; 73         } 74         if (y!=1) return false; 75     } 76     return true; 77 } 78 //pollar_rho 求n的一个质因子 79 //c 为测试函数中的常数 80 long long pollard_rho(long long n,int c) 81 { 82     long long x,y,d,i=1,k=2; 83     srand(time(0)); 84     x=rand()%(n-1)+1; 85     y=x; 86     while (true) 87     { 88          i++; 89          x=(mult_mod(x,x,n)+c)%n; 90          d=gcd(y-x,n); 91          if (d>1 && d<n) return d; 92          if (y==x) return n; 93          if (i==k) 94          { 95              y=x; 96              k<<=1; 97          } 98     } 99 }100 //找出n的所用质因子101 void findFactor(long long n,int c)102 {103     if (n==1) return ;104     if (miller_rabin(n,10))105     {106         factor[++factor_top]=n;107         return ;108     }109     long long p=n;110     while (p>=n)111     {112         p=pollard_rho(p,c--);113     }114     findFactor(p,c);115     findFactor(n/p,c);116 }117 long long a[1000];118 int m;119 int cmp(long long a,long long b)120 {121     return a>b;122 }123 void slove()124 {125     sort(factor,factor+factor_top+1,cmp);126     m=0;127     a[0]=factor[0];128     for (long long i=0;i<factor_top;i++)129     {130         if (factor[i]==factor[i+1])131         {132             a[m]*=factor[i];133         }134         else135         {136             m++;137             a[m]=factor[i+1];138         }139     }140 }141 long long minx,ans;142 void dfs(int s,long long num,long long t)143 {144     if (s==m+1)145     {146         if (minx==-1 || (num+t/num<minx))147         {148             minx=num+t/num;149             ans=num;150         }151         return ;152     }153     dfs(s+1,a[s]*num,t);154     dfs(s+1,num,t);155 }156 int main()157 {158     __int64 s,t,n;159     while (scanf("%I64d%I64d",&s,&t)!=EOF)160     {161         n=t/s;162         if (s==t)163         {164             printf("%I64d %I64d\n",s,t);165             continue;166         }167         //printf("%I64d\n",gcd(t,s));168         factor_top=-1;169         findFactor(n,107);170         //printf("findFactor()\n");171         m=0;172         slove();173         //printf("slove()\n");174         minx=-1;175         dfs(0,1,n);176         //printf("dfs()\n");177         if (ans>n/ans) ans=n/ans;178         printf("%I64d %I64d\n",ans*s,n/ans*s);179     }180     return 0;181 }