$Pollard$ - $Rho$

求出 $n$ 的所有素因子。采用椭圆曲线分解法，先用 $millar$ - $rabin$ 判断是否是质数，若不是，为了更大概率地找到可能的因子，随机选取许多数 $x_1,x_2,\dots,x_m$ 判断是否存在 $gcd(|x_i-x_j|,n)>1$ 如果有，就找到了一个因子。 $pollard$ - $rho$ 构造出一列数再在相邻的数之间判断，数列的生成使用函数 $x_{n+1}=(x_n^2+k)\%n$ ，这个数列由鸽巢原理得必有循环节，数列形状看起来就像 $\rho$ ，采用高效的 $brent$ 判环法，每次只计算 $x_k$ ，当 $k$ 是二的方幂时 $y=x_k$ ，每次计算 $d=gcd(|x_k-y|,n)$ ，找到因子时分成两部分递归处理。复杂度 $O(n^{\frac 1 4})$

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstring>

using namespace std;

typedef long long ll;

ll testcases;

ll n;

ll read()

{

	register ll res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

ll prime[12] = {2ll,3ll,5ll,7ll,11ll,13ll,17ll,19ll,23ll,29ll,31ll,37ll};

inline ll mul(ll a,ll b,ll p)

{

	ll d = ((long double)a / p * b + 1e-8);

	ll r = a * b - d * p;

	return (r > 0 ? r : r + p);

}

inline ll power(ll a,ll b,ll p)

{

	register ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = mul(res,a,p);

		b = b >> 1;

		a = mul(a,a,p);

	}

	return res;

}

bool check(ll a,ll b,ll p)

{

	if((b & 1) == 1)return true;

	register ll t = power(a,(b >> 1),p);

	if(t == 1ll)return check(a,(b >> 1),p);

	else if(t == p - 1ll)return true;

	else return false;

}

inline bool test(ll n)

{

	if(n == 1ll)return false;

	if(n == 2ll)return true;

	if((n & 1) == 0)return false;

	for(int i = 0;i < 12;++i)

	{

		if(n == prime[i])return true;

		else if(power(prime[i],n - 1ll,n) != 1ll)return false;

		else if(!check(prime[i],n - 1ll,n))return false;

	}

	return true;

}

ll p[40];

int tot = 0;

ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b,a % b));}

inline ll rho(ll n, ll c)

{

    ll x = rand() % n,y = x,t = 1;

    for(int i = 1,k = 2;t == 1;++i)

	{

        x = (mul(x,x,n) + c) % n;

        t = gcd(abs(x - y),n);

        if(i == k)y = x,k <<= 1;

    }

    return t;

}

bool solve(ll n)

{

	if(n == 1)return false;

	if(test(n)){p[++tot] = n;return true;}

	register ll t = n;

	while(t == n)

	{

		t = rho(n,rand() % 5 + 1);

	}

	solve(t);

	solve(n / t);

	return false;

}

int main()

{

	srand(time(NULL));

	while(scanf("%lld",&n) && n != 0)

	{

		tot = 0;

		memset(p,0,sizeof(p));

		solve(n);

		sort(p + 1,p + 1 + tot);

		register int cnt = 1;

		for(int i = 2;i <= tot + 1;++i)

		{

			if(p[i] != p[i - 1])

			{

				printf("%lld^%d ",p[i - 1],cnt);

				cnt = 1;

			}

			else

			{

				++cnt;

			}

		}

		puts("");

	}

	return 0;

}