/*
Time:2019.12.11
Author: Goven
type:pollard-rho大数分解质因子+Miller_Rabin判断质数
ref:
*/
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
int cnt = 0;
ll factor[1000];
ll Mult_mod (ll a, ll b, ll mod) {//大数乘法
a %= mod;
b %= mod;
ll res = 0;
while (b) {
if (b & 1) res = (res + a) % mod;
a = (a << 1) % mod;
b >>= 1;
}
return res;
}
ll pow_mod (ll a, ll b, ll mod) {
a %= mod;
ll res = 1;
while (b) {
if (b & 1) res = Mult_mod(res, a, mod);
a = Mult_mod(a, a, mod);
b >>= 1;
}
return res;
}
bool Check (ll a, ll x, ll t, ll mod) {//二次探测判断是否为合数
a = pow_mod(a, x, mod);
ll last;
for (int i = 0; i < t; i++) {
last = a;
a = Mult_mod(a, a, mod);
if (a == 1 && last != 1 && last != mod - 1) return true;
}
if (a != 1) return true;
return false;
}
bool Miller_Rabin (ll n, int k) {//Miller_Rabin判断素数
if (n < 2) return false;
if (n == 2) return true;
if (n & 1 == 0) return false;//step1:粗筛
//step2:二次探测
ll t = 0, x = n - 1;//att1: x这里的赋值别忘了减1
while (x & 1 == 0) x >>= 1, t++;
for (int i = 0; i < k; i++) {
ll a = rand() % (n - 1) + 1;
if (Check(a, x, t, n))
return false;
}
return true;
}
ll gcd (ll a, ll b) {
if (a < 0) return gcd(-a, b);
return b ? gcd(b, a % b) : a;
}
ll f (ll x, ll c, ll mod) {//生成随机数:f(x) = (x * x + c) % mod
return (Mult_mod(x, x, mod) + c) % mod;
}
ll Pollard_rho (ll n, ll c) {//Pollard_rho找到n的某个因子
ll a = rand() % n;
ll b = a;
ll i = 1, k = 2;
while (1) {
i++;
a = f(a, c, n);
ll d = gcd(a - b, n);
if (d != 1 && d != n) return d;
if (a == b) return n;//到了随机数的循环节
if (i == k) {
b = a;
k += k;
}
}
}
void findFac (ll n) {//求解n的素因子
if (Miller_Rabin(n, 5)) {
factor[cnt++] = n;
return;
}
ll p = n;
while (p >= n) p = Pollard_rho(p, (ll)rand() % (n - 1) + 1);
findFac(p);
findFac(n / p);
}
bool isPrime (int x) {
for (int i = 2; i <= x >> 1; i++) {
if (x % i == 0) return false;
}
return true;
}
int main()
{
srand(time(NULL));
int k;
cin >> k;
ll n;
for (int i = 2; i <= k; i++) {
if (!isPrime(i)) continue;
n = ((ll)1 << i ) - 1;//err1:1前面要加(ll)
cnt = 0;
findFac(n);
if (cnt == 1) continue;
sort(factor, factor + cnt);
printf("%lld", factor[0]);
for (int j = 1; j < cnt; j++) {
printf(" * %lld", factor[j]);
}
printf(" = %lld = ( 2 ^ %d ) - 1\n", n, i);
}
return 0;
}
poj2191 pollard-rho大数分解质因子+Miller_Rabin判断质数
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...