【代码超详解】洛谷 P4718 【模板】Pollard-Rho算法（要求一并使用：快速幂取模、快速积取模、Miller-Rabin算法）

一、题目描述

输入输出样例

输入 #1

6
2
13
134
8897
1234567654321
1000000000000

输出 #1

Prime
Prime
67
41
4649
5

说明/提示

2018.8.14 新加数据两组，时限加大到2s，感谢 @whzzt

by @will7101

二、算法分析说明与代码编写指导

三、AC 代码：

1、这题采用__int128作为中间类型的快速幂取模配合Miller-Rabin算法比采用long double作为中间类型时要快，原因不明。
2、采用long double作为中间变量的快速积取模配合Pollard-Rho算法比采用__int128类型作为中间变量时要快，原因不明。
3、Pollard-Rho算法中当 j % 127 == 0 时提前计算GCD是为什么，我也不知道：

if (j % 127 == 0) { d = gcd((_Ty)M, n); if (d > 1)return d; }

4、Pollard-Rho算法只能返回一个数的一个非平凡因子。题目要求当数不是质数时，输出这个数的最大质因子。此时要对Pollard-Rho算法的返回值进行素性检验，如果不是素数，就要继续递归分解。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<ctime>
#pragma warning(disable:4996)
using namespace std;
long long x, MaxPrimeDivisor, prime[] = { 2,3,5,7,11,13,17,19,23,29,31,37 }, * prime_end = prime + sizeof(prime) / sizeof(prime[0]); unsigned T;
template<typename _RTy, typename _Ty1, typename _Ty2, typename _Ty3> inline _RTy PowerMod(const _Ty1& radix, const _Ty2& exp, const _Ty3& mod) {
	__int128 ans = 1, R = radix % mod, X = exp, M = mod;
	while (X) {
		if (X & 1)ans = (ans * R) % M;
		X >>= 1, R = (R * R) % M;
	}return ans % M;
}
template<typename _Ty> inline bool MillerRabin(const _Ty& x) {
	for (auto B = prime; B != prime_end; ++B) {
		if (x == *B)return true;
		if (x < *B)return false;
		_Ty y = x - 1, x0 = y, r = PowerMod<_Ty>(*B, y, x);
		if (r != 1)return false;
		for (; (y & 1) == 0 && r == 1;) {
			y >>= 1, r = PowerMod<_Ty>(*B, y, x); if (r != 1 && r != x0)return false;
		}
	}
	return true;
}
template<typename _Ty> _Ty gcd(const _Ty& a, const _Ty& b) {
	return b == 0 ? a : gcd(b, a % b);
}//不要输入a = 0，否则会返回错误的结果！
template<typename _Ty> inline _Ty MultiModL(const _Ty& a, const _Ty& b, const _Ty& mod) {
	return (a * b - (_Ty)((long double)a / mod * b) * mod + mod) % mod;
}
template<typename _Ty> inline _Ty PollardRho(const _Ty& n) {
	_Ty c = rand(), d, s = 0, t = 0, M = 1; unsigned i, j;
	for (i = 1;; i <<= 1, s = t, M = 1) {
		for (j = 1; j <= i; ++j) {
			t = (MultiModL(t, t, x) + c) % n, M = MultiModL(M, abs(s - t), n);
			if (j % 127 == 0) { d = gcd((_Ty)M, n); if (d > 1)return d; }
		}
		d = gcd(M, n); if (d > 1)return d;
	}
}
void GetMaxPrimeDivisor(long long n) {
	if (n == 1)return;
	if (MillerRabin(n)) { MaxPrimeDivisor = max(MaxPrimeDivisor, n); return; }
	long long d = PollardRho(n);
	while (n % d == 0)n /= d;
	GetMaxPrimeDivisor(d); GetMaxPrimeDivisor(n);
}
int main() {
	srand(time(0));
	scanf("%u", &T); ++T;
	while (--T) {
		scanf("%lld", &x); MaxPrimeDivisor = 0;
		GetMaxPrimeDivisor(x);
		if (MaxPrimeDivisor == x)puts("Prime");
		else printf("%lld\n", MaxPrimeDivisor);
	}
	return 0;
}