思路：
题目链接http://poj.openjudge.cn/practice/C18H/
用2147483647除以最大素因子。
这里用了Pollard_rho因子分解算法，模板参考了http://www.cnblogs.com/kuangbin/archive/2012/08/19/2646396.html
实现：
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <time.h> 5 #include <iostream> 6 #include <algorithm> 7 #include <map> 8 using namespace std; 9 typedef long long ll; 10 //**************************************************************** 11 // Miller_Rabin 算法进行素数测试 12 //速度快，而且可以判断 <2^63的数 13 //**************************************************************** 14 const int S = 5;//随机算法判定次数，S越大，判错概率越小 15 16 //计算 (a*b)%c. a,b都是ll的数，直接相乘可能溢出的 17 // a,b,c <2^63 18 ll mult_mod(ll a, ll b, ll c) 19 { 20 a %= c; 21 b %= c; 22 ll ret = 0; 23 while (b) 24 { 25 if (b & 1) { ret += a; ret %= c; } 26 a <<= 1; 27 if (a >= c) a %= c; 28 b >>= 1; 29 } 30 return ret; 31 } 32 33 //计算 x^n %c 34 ll pow_mod(ll x, ll n, ll mod)//x^n%c 35 { 36 if (n == 1) return x % mod; 37 x %= mod; 38 ll tmp = x; 39 ll ret = 1; 40 while (n) 41 { 42 if (n & 1) ret = mult_mod(ret, tmp, mod); 43 tmp = mult_mod(tmp, tmp, mod); 44 n >>= 1; 45 } 46 return ret; 47 } 48 49 //以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数 50 //一定是合数返回true,不一定返回false 51 bool check(ll a, ll n, ll x, ll t) 52 { 53 ll ret = pow_mod(a, x, n); 54 ll last = ret; 55 for (int i = 1; i <= t; i++) 56 { 57 ret = mult_mod(ret, ret, n); 58 if (ret == 1 && last != 1 && last != n - 1) return true;//合数 59 last = ret; 60 } 61 if (ret != 1) return true; 62 return false; 63 } 64 65 // Miller_Rabin()算法素数判定 66 //是素数返回true.(可能是伪素数，但概率极小) 67 //合数返回false; 68 69 bool Miller_Rabin(ll n) 70 { 71 if (n < 2) return false; 72 if (n == 2) return true; 73 if ((n & 1) == 0) return false;//偶数 74 ll x = n - 1; 75 ll t = 0; 76 while ((x & 1) == 0) { x >>= 1; t++; } 77 for (int i = 0; i < S; i++) 78 { 79 ll a = rand() % (n - 1) + 1;//rand()需要stdlib.h头文件 80 if (check(a, n, x, t)) 81 return false;//合数 82 } 83 return true; 84 } 85 86 //************************************************ 87 //pollard_rho 算法进行质因数分解 88 //************************************************ 89 ll factor[100];//质因数分解结果（刚返回时是无序的） 90 int tol;//质因数的个数。数组小标从0开始 91 92 ll gcd(ll a, ll b) 93 { 94 if (a == 0) return 1; 95 if (a < 0) return gcd(-a, b); 96 while (b) 97 { 98 ll t = a % b; 99 a = b; 100 b = t; 101 } 102 return a; 103 } 104 105 ll Pollard_rho(ll x, ll c) 106 { 107 ll i = 1, k = 2; 108 ll x0 = rand() % x; 109 ll y = x0; 110 while (1) 111 { 112 i++; 113 x0 = (mult_mod(x0, x0, x) + c) % x; 114 ll d = gcd(y - x0, x); 115 if (d != 1 && d != x) return d; 116 if (y == x0) return x; 117 if (i == k) { y = x0; k += k; } 118 } 119 } 120 //对n进行素因子分解 121 void findfac(ll n) 122 { 123 if (Miller_Rabin(n))//素数 124 { 125 factor[tol++] = n; 126 return; 127 } 128 ll p = n; 129 while (p >= n) p = Pollard_rho(p, rand() % (n - 1) + 1); 130 findfac(p); 131 findfac(n / p); 132 } 133 134 int main() 135 { 136 srand(time(NULL));//需要time.h头文件//POJ上G++不能加这句话 137 ll n; 138 while (scanf("%lld", &n) != EOF && n) 139 { 140 tol = 0; 141 findfac(n); 142 sort(factor, factor + tol); 143 ll ans = ((1ll << 31) - 1) / factor[tol - 1]; 144 printf("%lld ", ans); 145 } 146 return 0; 147 }