抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

暴力枚举因子法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//素数筛与合数分解
//预处理O(sqrt(n)),询问O(sqrt(n))
//调用find_ini() getfac()
const int maxn=3e6+5;
int prime[maxn],prime_,not_prime[maxn]={1,1};

void prime_ini(){// 素数不可能筛到longlong范围
for(int i=2; i<maxn; i++){
if(!not_prime[i])prime[prime_++]=i;//把质数收录
for(int j=0; 1ll*i*prime[j]<maxn; j++){
not_prime[i*prime[j]]=1;//对每一个数字枚举他的最小因子
if(i%prime[j]==0)break;//在往后的话就不是最小因子了
}
}
}

int fac[100][2],fac_;
void getfac(int x){ // assert(x>=2)
fac_=0;//清空fac
for(int i=0; prime[i]<=x/prime[i]; i++){
if(x%prime[i]==0){
fac[fac_][0]=prime[i];
fac[fac_][1]=0;
while(x%prime[i]==0){
fac[fac_][1]++;
x/=prime[i];
}
fac_++;
}
}
if(x!=1){
fac[fac_][0]=x;
fac[fac_][1]=1;
fac_++;
}
}

记录最小因子法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

//这个板子只能处理正数
//预处理O(n)合数分解O(lgn)
//最大使用范围[1,MAXN),实际使用[1,MAXN);
//调用find_ini() getfac()
typedef long long ll;
const ll MAXN=1e6+5;
ll prime[MAXN],prime_;
ll min_fac[MAXN]={-9527,1};//0,1
bool not_prime[MAXN]={true,true};//0,1

void prime_ini(){
for(ll i=2; i<MAXN; i++){
if(!not_prime[i]){
prime[prime_++]=i;//把质数收录
min_fac[i]=i;
}

for(ll j=0; j<prime_ && i*prime[j]<MAXN; j++){
not_prime[i*prime[j]]=true;//对每一个数字枚举他的最小因子
min_fac[i*prime[j]]=prime[j];
if(i%prime[j]==0)break;//在往后的话就不是最小因子了
}
}
}

//当x=0,1会异常,无意义的东西
ll fac[100][2],fac_;
void getfac(int x){
fac_=0;
while(x!=1){
ll little=min_fac[x];
fac[fac_][0]=little;
fac[fac_][1]=0;
while(little!=1 && min_fac[x]==little){
x/=little;
fac[fac_][1]++;
}
fac_++;
}
}
//solved poj-1365

PollaraRho随机分解法

我们使用米勒罗宾素数测试多次,只要无法通过测试,则这个数必然是合数,然后使用PollaraRho随机分解法对素数进行分解。考虑gcd,如果$gcd(a,b)$不为1或者b,那么这个数一定是b的因子,可以用来分解b,一个数的因子很少,但是和gcd不为1或b的数有很多个(至少是$\sqrt{b}$个),所以我们多次随机生成,一定能够得到他的因子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 I;
/*
* 素数
* 欧拉定理
* 费马小定理1 若a为整数,p为质数,则 pow(a,p)%p=a%p
* 费马小定理2 若a为整数,p为质数,a不是p的倍数 则 pow(a,p-1)%p=1%p=1 (0是2的0倍)
*/
namespace amazing{
inline ll gcd(ll a,ll b){
int shift=__builtin_ctzll(a|b);
b>>=__builtin_ctzll(b);
while(a){
a>>=__builtin_ctzll(a);
if(a<b) swap(a,b);
a-=b;
}return b<<shift;
}
inline ll mul(ll x,ll y,ll p){// 有误差,要当心使用,wa了可能就是因为他
ll z=(long double)x/p*y;
ll res=x*y-z*p;
return res<p?res+p:res>p?res-p:res;
}
}

ll qpow(ll a,ll b,ll c){
ll r=1;
while(b){
if(b&1) r=I(r)*a%c;
a=I(a)*a%c;
b>>=1;
}return r;
}
bool miller_rabin(ll n){// O(10*lgn)
if(n<=1) return false;
ll t=n-1,k=0;
while((t&1)==0) t>>=1,k++;
for(int i=1;i<=10;i++){// 8-10次
ll a=qpow(rand()%(n-1)+1,t,n);//全部复杂度在这
for(ll j=1;j<=k;j++){
ll nex=I(a)*a%n;
if(nex==1&&a!=1&&a!=n-1) return false;//通不过测试,是合数
a=nex;
}
if(a!=1)return false;//通不过测试,是合数
}
return true;// 通过测试可能是伪素数
}
ll pollard_rho(ll n){ // assert(n>1)
while(true){
ll c=rand()%(n-1)+1;
ll x=0,y=0,val=1;
for(ll i=0;;i++){
x=amazing::mul(x,x,n)+c;
if(x>n)x-=n;
// x=(I(x)*x+c)%n;
if(x==y) break;
val=amazing::mul(val,abs(x-y),n);
// val=I(val)*abs(x-y)%n;// 乘起来是根据 gcd(a,n)|gcd(ab,n)恒成立 且gcd(ab,n)=gcd(ab%n,n)
if((i&-i)==i||i%127==0){// 太多必然导致val趋于n,太少导致gcd拖慢速度
ll d=__gcd(val,n);// 乘起来一起算
if(d==n) break;
if(d>1) return d;
}
if((i&-i)==i) y=x;
}
}
}

vector<ll> findfac(ll n){
vector<ll>res,stk(1,n);
if(stk.back()==1) return res;
while(!stk.empty()){
ll top=stk.back();stk.pop_back();
if(miller_rabin(top)) res.push_back(top);
else{// 通不过测试是合数
ll fac=pollard_rho(top);
stk.push_back(fac);
stk.push_back(top/fac);
}
}
return res;
}

ll read(){ll x;scanf("%lld",&x);return x;}

int main(){
srand(time(NULL));
for(int T=read();T>=1;T--){
vector<ll>v=findfac(read());
sort(v.begin(),v.end());
if(v.size()==1) printf("Prime\n");
else printf("%lld\n",v.back());
}
}

评论