思路:a/n*b/n=lcm/gcd 所以这道题就是分解ans.dfs枚举每种素数情况。套Miller_Rabin和pollard_rho模板
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 //#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<iostream> 6 #include<queue> 7 #include<stack> 8 #include<cmath> 9 #include<set> 10 #include<algorithm> 11 #include<vector> 12 // #include<malloc.h> 13 using namespace std; 14 #define clc(a,b) memset(a,b,sizeof(a)) 15 #define inf (LL)1<<61 16 #define LL long long 17 const double eps = 1e-5; 18 const double pi = acos(-1); 19 // inline int r(){ 20 // int x=0,f=1;char ch=getchar(); 21 // while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();} 22 // while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 23 // return x*f; 24 // } 25 const int Times = 10; 26 const int N = 5500; 27 28 LL n, m, ct, cnt; 29 LL minn, mina, minb, ans; 30 LL fac[N], num[N]; 31 32 LL gcd(LL a, LL b) 33 { 34 return b? gcd(b, a % b) : a; 35 } 36 37 LL multi(LL a, LL b, LL m) 38 { 39 LL ans = 0; 40 a %= m; 41 while(b) 42 { 43 if(b & 1) 44 { 45 ans = (ans + a) % m; 46 b--; 47 } 48 b >>= 1; 49 a = (a + a) % m; 50 } 51 return ans; 52 } 53 54 LL quick_mod(LL a, LL b, LL m) 55 { 56 LL ans = 1; 57 a %= m; 58 while(b) 59 { 60 if(b & 1) 61 { 62 ans = multi(ans, a, m); 63 b--; 64 } 65 b >>= 1; 66 a = multi(a, a, m); 67 } 68 return ans; 69 } 70 71 bool Miller_Rabin(LL n) 72 { 73 if(n == 2) return true; 74 if(n < 2 || !(n & 1)) return false; 75 LL m = n - 1; 76 int k = 0; 77 while((m & 1) == 0) 78 { 79 k++; 80 m >>= 1; 81 } 82 for(int i=0; i<Times; i++) 83 { 84 LL a = rand() % (n - 1) + 1; 85 LL x = quick_mod(a, m, n); 86 LL y = 0; 87 for(int j=0; j<k; j++) 88 { 89 y = multi(x, x, n); 90 if(y == 1 && x != 1 && x != n - 1) return false; 91 x = y; 92 } 93 if(y != 1) return false; 94 } 95 return true; 96 } 97 98 LL pollard_rho(LL n, LL c) 99 { 100 LL i = 1, k = 2; 101 LL x = rand() % (n - 1) + 1; 102 LL y = x; 103 while(true) 104 { 105 i++; 106 x = (multi(x, x, n) + c) % n; 107 LL d = gcd((y - x + n) % n, n); 108 if(1 < d && d < n) return d; 109 if(y == x) return n; 110 if(i == k) 111 { 112 y = x; 113 k <<= 1; 114 } 115 } 116 } 117 118 void find(LL n, int c) 119 { 120 if(n == 1) return; 121 if(Miller_Rabin(n)) 122 { 123 fac[ct++] = n; 124 return ; 125 } 126 LL p = n; 127 LL k = c; 128 while(p >= n) p = pollard_rho(p, c--); 129 find(p, k); 130 find(n / p, k); 131 } 132 133 void dfs(LL dept, LL tem=1) 134 { 135 if(dept == cnt) 136 { 137 LL a = tem; 138 LL b = ans / a; 139 if(gcd(a, b) == 1) 140 { 141 a *= n; 142 b *= n; 143 if(a + b < minn) 144 { 145 minn = a + b; 146 mina = a; 147 minb = b; 148 } 149 } 150 return ; 151 } 152 for(int i=0; i<=num[dept]; i++) 153 { 154 if(tem > minn) return; 155 dfs(dept + 1, tem); 156 tem *= fac[dept]; 157 } 158 } 159 160 int main() 161 { 162 while(~scanf("%llu %llu", &n, &m)) 163 { 164 if(n == m) 165 { 166 printf("%llu %llu ",n,m); 167 continue; 168 } 169 minn = inf; 170 ct = cnt = 0; 171 ans = m / n; 172 find(ans, 120); 173 sort(fac, fac + ct); 174 num[0] = 1; 175 int k = 1; 176 for(int i=1; i<ct; i++) 177 { 178 if(fac[i] == fac[i-1]) 179 ++num[k-1]; 180 else 181 { 182 num[k] = 1; 183 fac[k++] = fac[i]; 184 } 185 } 186 cnt = k; 187 dfs(0, 1); 188 if(mina > minb) swap(mina, minb); 189 printf("%llu %llu ",mina, minb); 190 } 191 return 0; 192 }