题意：一个长为n（n<2^63）的管子，在管子上做标记，每隔L个长度单位做一个标记，从管子头端开始，保证最后一次标记恰好在管子的尾端。让你找出有多少个这样的L（L<n），且他们之间两两互素，然后求出这些L的和最大值。
分析：转换一下就是求n有多少个质因子用pollard_rho大整数分解分解n，因为素数之间两两互质，所以每段L都由每个质因子的k次幂组成，如果n是素数，由于L<n，所以只能L==1
收获：接触到随机算法
代码：
/************************************************
* Author :Running_Time
* Created Time :2015-8-28 14:38:38
* File Name :E.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int S = 20;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7; ll GCD(ll a, ll b) {
if (a == 0) return 1;
if (a < 0) a = -a;
while (b) {
ll c = a % b;
a = b; b = c;
}
return a;
} ll multi_mod(ll a, ll b, ll p) {
ll ret = 0;
a %= p; b %= p;
while (b) {
if (b & 1) {
ret += a;
if (ret >= p) ret -= p;
}
a <<= 1;
if (a >= p) a -= p;
b >>= 1;
}
return ret;
} ll pow_mod(ll a, ll x, ll p) {
ll ret = 1;
a %= p;
while (x) {
if (x & 1) ret = multi_mod (ret, a, p);
a = multi_mod (a, a, p);
x >>= 1;
}
return ret;
} bool check(ll a, ll n, ll x, int t) {
ll ret = pow_mod (a, x, n);
ll last = ret;
for (int i=1; i<=t; ++i) {
ret = multi_mod (ret, ret, n);
if (ret == 1 && last != 1 && last != n - 1) return true; //合数
last = ret;
}
if (ret != 1) return true;
return false;
} bool Miller_Rabin(ll n) {
if (n == 2) return true;
if (n < 2 || ! (n & 1)) return false; //偶数或1
ll x = n - 1; int t = 0;
while (! (x & 1)) {
x >>= 1; t++;
}
for (int i=1; i<=S; ++i) {
ll a = rand () % (n - 1) + 1;
if (check (a, n, x, t)) return false; //合数
}
return true;
} ll Pollard_rho(ll x, ll c) {
ll i = 1, k = 2;
ll a = rand () % x;
ll b = a;
while (1) {
i++;
a = (multi_mod (a, a, x) + c) % x;
ll d = GCD (b - a, x);
if (d != 1 && d != x) return d;
if (b == a) return x;
if (i == k) b = a, k += k;
}
} void factorize(ll n, vector<ll> &ret) {
if (Miller_Rabin (n)) {
ret.push_back (n); return ;
}
ll p = n;
while (p >= n) p = Pollard_rho (p, rand () % (n - 1) + 1);
factorize (p, ret);
factorize (n / p, ret);
} int main(void) {
srand (time (NULL));
int T; scanf ("%d", &T);
while (T--) {
ll n; scanf ("%I64d", &n);
vector<ll> ret;
factorize (n, ret);
sort (ret.begin (), ret.end ());
ll sum = 0, cnt = 0;
for (int i=0; i<ret.size (); ++i) {
ll tmp = ret[i];
while (i + 1 < ret.size () && ret[i] == ret[i+1]) tmp *= ret[i++];
sum += tmp; cnt++;
} if (cnt == 1) sum /= ret[0];
printf ("%I64d %I64d\n", cnt, sum);
} return 0;
}