P4718 【模板】Pollard-Rho算法

全部 $\texttt{TLE}$ ，求算法优化或者卡常

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

using namespace std;

typedef long long LL;

const LL test[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
LL ans = -0x3f3f3f3f;
int T;
LL n;

namespace Functions {
	LL gcd(LL a, LL b) {
		return !b ? a : gcd(b, a % b);
	}
	LL qpow(LL a, LL b, LL p) {
		LL res = 1;
		while (b) {
			if (b & 1) res = res * a % p;
			a = a * a % p;
			b >>= 1;
		}
		return res;
	}
	LL mul(LL a, LL b, LL p) {
		LL res = 0;
		while (b) {
			if (b & 1) res = (res + a) % p;
			a = (a + a) % p;
			b >>= 1;
		}
		return res;
	}
	bool Miller_Rabin(LL n) { // 判断 n 是否是质数 
		if (n == 1) return false;
		LL t = n - 1, k = 0;
		while (!(t & 1)) t >>= 1, k ++ ;
		
		for (int i = 0; i < 8; i ++ ) {
			if (n == test[i]) return true;
			LL a = qpow(test[i], t, n), ne = a;
			for (int i = 1; i <= k; i ++ ) {
				ne = a * a % n;
				if (ne == 1 && a != 1 && a != n - 1) return false;
				a = ne;
			}
			if (a != 1) return false;
		}
		return true;
	}
}
using namespace Functions;

LL Pollard_Rho(LL n) { // 分解 n  
	if (n == 4) return 2;
	if (Miller_Rabin(n)) return n;
	LL c = rand() % (n - 1) + 1;
	auto f = [=](LL x) {return (mul(x, x, n) + c) % n; };
	LL x = f(0), y = f(f(0));
	
	for (int lim = 1; x != y; lim = min(lim << 1, 128)) {
		LL cnt = 1;
		for (int i = 0; i < lim; i ++ ) {
			cnt = mul(cnt, abs((x - y) % n), n);
			if (!cnt) break;
			x = f(x), y = f(f(y));
		}
		if (gcd(cnt, n) != 1) return gcd(cnt, n);
	}
	return n;
}

void max_factor(LL n) {
	if (Miller_Rabin(n))
		return ans = max(ans, n), void();
	LL d = Pollard_Rho(n);
	while (d == n) d = Pollard_Rho(n);
	if (Miller_Rabin(d)) ans = max(ans, d);
	else max_factor(d);
	d = n / d;
	if (Miller_Rabin(d)) ans = max(ans, d);
	else max_factor(d);
}

int main() {
// 	freopen("std.in", "r", stdin);
// 	freopen("my.out", "w", stdout);
	
	srand(time(0));
	scanf("%d", &T);
	while (T -- ) {
		scanf("%lld", &n); 
		ans = -0x3f3f3f3fll;
		if (Miller_Rabin(n)) puts("Prime");
		else max_factor(n), printf("%lld\n", ans);
	}
	
	return 0;
}