模板，pollard_rho大数因数分解

大数分解，没有模板你就OUT啦。。。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;
typedef long long LL;

long long factor[110],cnt;
long long Mul_Mod(long long a,long long b,long long c) {
    if (b == 0)
        return 0;
    long long ans = Mul_Mod(a,b / 2,c);
    ans = (ans * 2) % c;
    if (b % 2)
        ans = (ans + a) % c;
    return ans;
}
long long Pow_Mod(long long a,long long c) {
    if (b == 0)
        return 1;
    long long x = Pow_Mod(a,c);
    if (x == 0)
        return 0;
    long long y = Mul_Mod(x,x,c);
    if (y == 1 && x != 1 && x != c - 1)
        return 0;
    if (b % 2)
        y = Mul_Mod(y,a,c);
    return y;
}
bool Miller_rabin(long long n,int timenum = 10) {
    if (n < 2)
        return false;
    if (n == 2)
        return true;
    while (timenum--) {
        if (Pow_Mod(rand() % (n - 2) + 2,n - 1,n) != 1)
            return false;
    }
    return true;
}
long long Gcd(long long a,long long b) {
    long long t;
    while (b) {
        t = a;
        a = b;
        b = t % b;
    }
    return a;
}
void Pollard(long long n);

void Factor(long long n) {
    long long d = 2;
    while (true) {
        if (n % d == 0) {
            Pollard(d);
            Pollard(n / d);
            return;
        }
        d++;
    }
}
void Pollard(long long n) {
    if (n <= 0)
        printf("errorn");
    if (n == 1)
        return;
    if (Miller_rabin(n)) {
        factor[cnt++] = n;
        return;
    }
    long long i = 0,k = 2,y,d;
    x = y = rand() % (n - 1) + 1;
    while (i++ < 123456) {
        x = (Mul_Mod(x,n) + n - 1) % n;
        d = Gcd((y - x + n) % n,n);
        if (d != 1) {
            Pollard(d);
            Pollard(n / d);
            return;
        }
        if (i == k) {
            y = x;
            k *= 2;
        }
    }
    Factor(n);
}


int main() {
    int Case;
    long long n;
    scanf("%d",&Case);
    while (Case--) {
        scanf("%lld",&n);
        if (Miller_rabin(n))
            printf("Primen");
        else {
            cnt = 0;
            Pollard(n);
            sort(factor,factor + cnt);
            for(int i=0;i<cnt;i++) 
            printf("%lldn",factor[i]);
        }
    }
    return 0;
}