RT，Pollard-Rho 不知道为什么 WA 了 /kk

代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef long long ll;
typedef __int128 lll;

const int N = 9, M = (1 << 7) - 1;
int test_prime[N + 7] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23};

inline ll quick_pow(ll x, ll p, ll mod){
	ll ans = 1;
	while (p){
		if (p & 1) ans = (lll)ans * x % mod;
		x = (lll)x * x % mod;
		p >>= 1;
	}
	return ans;
}

inline bool miller_rabin(ll n, ll k){
	ll nd = n - 1, m = nd;
	while (m){
		ll x = quick_pow(k, m, n);
		if (x != 1 && x != nd) return false;
		if ((m & 1) == 1 || x == nd) return true;
		m >>= 1;
	}
	return true;
}

inline bool is_prime(ll n){
	if (n < 2) return false;
	for (register int i = 1; i <= N; i++){
		if (n == test_prime[i]) return true;
		if (!miller_rabin(n, test_prime[i])) return false;
	}
	return true;
}

inline ll floyd(ll a, ll b, ll p){
	return ((lll)a * a % p + b) % p;
}

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

inline ll pollard_pho(ll n){
	ll x = 0, c = rand() % (n - 1) + 1;
	for (register int i = 1; ; i <<= 1){
		ll y = 1, z = x, ans;
		for (register int j = 1; j <= i; j++){
			x = floyd(x, c, n);
			y = (lll)y * abs(x - z) % n;
			if (j % M == 0){
				ans = gcd(n, y);
				if (ans > 1) return ans;
			}
		}
		ans = gcd(n, y);
		if (ans > 1) return ans;
	}
}

void max_factor(ll n, ll &ans){
	if (n < 2 || n <= ans) return;
	if (is_prime(n)){
		if (ans < n) ans = n;
		return;
	}
	ll factor;
	do {
		factor = pollard_pho(n);
	} while (factor == n);
	while (n % factor == 0){
		n /= factor;
	}
	max_factor(n, ans);
	max_factor(factor, ans);
}

int main(){
	ll n;
	while (scanf("%lld", &n) != EOF){
		if (n == 0) break;
		if (n == 1){
			printf("-1\n");
			continue;
		}
		ll ans = 0;
		srand(time(NULL));
		max_factor(n, ans);
		if (ans == n){
			printf("-1\n");
		} else {
			printf("%lld\n", ans);
		}
	}
	return 0;
}