대수 분해 pollardrho
8273 단어 po
#include<iostream>
#include<algorithm>
using namespace std;
long long factor[110], cnt;
long long Mul_Mod(long long a, long long b, long long c) {
if (b == 0)
return 0;
long long ans = Mul_Mod(a, b / 2, c);
ans = (ans * 2) % c;
if (b % 2)
ans = (ans + a) % c;
return ans;
}
long long Pow_Mod(long long a, long long b, long long c) {
if (b == 0)
return 1;
long long x = Pow_Mod(a, b / 2, c);
if (x == 0)
return 0;
long long y = Mul_Mod(x, x, c);
if (y == 1 && x != 1 && x != c - 1)
return 0;
if (b % 2)
y = Mul_Mod(y, a, c);
return y;
}
bool Miller_rabin(long long n, int timenum = 10) {
if (n < 2)
return false;
if (n == 2)
return true;
while (timenum--) {
if (Pow_Mod(rand() % (n - 2) + 2, n - 1, n) != 1)
return false;
}
return true;
}
long long Gcd(long long a, long long b) {
long long t;
while (b) {
t = a;
a = b;
b = t % b;
}
return a;
}
void Pollard(long long n);
void Factor(long long n) {
long long d = 2;
while (true) {
if (n % d == 0) {
Pollard(d);
Pollard(n / d);
return;
}
d++;
}
}
void Pollard(long long n) {
if (n <= 0)
printf("error
");
if (n == 1)
return;
if (Miller_rabin(n)) {
factor[cnt++] = n;
return;
}
long long i = 0, k = 2, x, y, d;
x = y = rand() % (n - 1) + 1;
while (i++ < 123456) {
x = (Mul_Mod(x, x, n) + n - 1) % n;
d = Gcd((y - x + n) % n, n);
if (d != 1) {
Pollard(d);
Pollard(n / d);
return;
}
if (i == k) {
y = x;
k *= 2;
}
}
Factor(n);
}
int main() {
int Case;
long long n;
scanf("%d", &Case);
while (Case--) {
scanf("%lld", &n);
if (Miller_rabin(n))
printf("Prime
");
else {
cnt = 0;
Pollard(n);
sort(factor, factor + cnt);
printf("%lld
", factor[0]);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
쓰다important IE 와 Mozilla 의 레이아웃 차이 해결웹 디자이너 페이지 를 디자인 할 때 한 가지 문제 가 저 를 괴 롭 혔 습 니 다.메 인 메뉴 는 IE 와 다른(Mozilla,Opera 등)브 라 우 저 에 나타 난 효과 편차 2px 입 니 다.캡 처 는 다음 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.