对一个大质数进行质因数分解 需要引用miller-robin来判素数
一直写的gcd居然挂掉了... 以后用__gcd了
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define ull unsigned long long #define lb long double ll maxfac; inline ll ksc(ull x,ull y,ll p){//O(1)快速乘(防爆long long) return (x*y-(ull)((lb)x/p*y)*p+p)%p; } ll pow_mod(ll x, ll y, ll mod) { ll res = 1; while(y) { if(y & 1) res = ksc(res, x, mod); x = ksc(x, x, mod); y >>= 1; } return res; } ll ABS(ll x) { if(x < 0) return -x; return x; } inline bool mr(ll x,ll p){//mille rabin判质数 if(pow_mod(x, p-1, p) != 1) return false;//费马小定理 ll y = p - 1, z; while(!(y & 1)){ //二次探测 y >>= 1; z = pow_mod(x, y, p); if(z != 1 && z != p - 1) return false; if(z == p - 1) return true; } return true; } inline bool isprime(ll x) { if(x < 2) return false;//mille rabin判质数 if(x == 2 || x == 3 || x == 5 || x==7 || x == 43) return true; return mr(2, x) && mr(3, x) && mr(5, x) && mr(7, x) && mr(43, x); } inline ll rho(ll p){//求出p的非平凡因子 ll x, y, z, c, g; int i, j;//先摆出来(z用来存(y-x)的乘积) while(1){//保证一定求出一个因子来 y = x = rand() % p;//随机初始化 z = 1; c = rand() % p;//初始化 i = 0, j = 1;//倍增初始化 while(++i){//开始玄学生成 x = (ksc(x, x, p) + c) % p;//可能要用快速乘 z = ksc(z, ABS(y - x), p);//我们将每一次的(y-x)都累乘起来 if(x == y || !z) break;//如果跑完了环就再换一组试试(注意当z=0时,继续下去是没意义的) if(!(i % 127) || i == j){//我们不仅在等127次之后gcd我们还会倍增的来gcd g = __gcd(z, p); if(g > 1) return g; if(i == j) y = x ,j <<= 1;//维护倍增正确性,并判环(一箭双雕) } } } } inline void prho(ll p) { if(p <= maxfac) return; if(isprime(p)) { maxfac = p; return; } ll pi = rho(p);//我们一次必定能求的出一个因子,所以不用while while(p % pi == 0) p /= pi;//记得要除尽 prho(pi); prho(p); } int main() { int T; scanf("%d", &T); srand(time(0)); while(T--) { //srand(time(0)); ll x; scanf("%lld", &x); maxfac = 1; if(isprime(x)) puts("Prime"); else { prho(x); printf("%lld\n", maxfac); } } return 0; }View Code