pollard_rho 模板
程序员文章站
2022-08-18 11:39:27
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}ll quick_mult(ll a, ll b, ll mod) { ll ans = 0; while(b) { if(b & 1) ans = (ans + a) % mod; a = (a + a) % mod; b >>= 1; } return ans;}ll quick_po...
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
ll quick_mult(ll a, ll b, ll mod) {
ll ans = 0;
while(b) {
if(b & 1) ans = (ans + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return ans;
}
ll quick_pow(ll a, ll n, ll mod) {
ll ans = 1;
while(n) {
if(n & 1) ans = quick_mult(ans, a, mod);
a = quick_mult(a, a, mod);
n >>= 1;
}
return ans;
}
bool miller_rabin(ll n) {
if(n == 2) return true;
if(n < 2 || !(n & 1)) return false;
ll s = 0, d = n - 1;
while(!(d & 1)) {
d >>= 1;
s++;
}
for(int i = 1; i <= 11; i++) {
ll a = rand() % (n - 2) + 2;
ll now = quick_pow(a, d, n), pre = now;
for(int j = 1; j <= s; j++) {
now = quick_mult(now, now, n);
if(now == 1 && pre != 1 && pre != n - 1) return false;
pre = now;
}
if(now != 1) return false;
}
return true;
}
ll pollard_rho(ll n, int c) {
ll x, y, i = 1, k = 2;
x = y = rand() % (n - 2) + 2;
for( ; ; ) {
i++;
x = (quick_mult(x, x, n) + c) % n;
ll g = gcd(y - x, n);
if(g > 1 && g < n) return g;
if(x == y) return n;
if(i == k) y = x, k <<= 1;
}
}
vector<ll> fac;
void find_fac(ll n, int k) {
if(n == 1) return ;
if(miller_rabin(n)) {
fac.pb(n);
return ;
}
ll p = n;
int c = k;
while(p >= n) p = pollard_rho(p, c--);
find_fac(n / p, k);
find_fac(p, k);
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
return 0;
}
本文地址:https://blog.csdn.net/weixin_45483201/article/details/107563376