Miller_Rabin质数判定 & Pollard_rho质因数分解 【POJ1811】 (2022CCPC网络赛H)

发表于 更新于 分类于

Miller_Rabin质数判定 & Pollard_rho质因数分解

  Miller_Rabin(x)返回true代表x是质数。Findfac(n)对n进行质因数分解，结果保存在数组factor中下标从0开始用，tol是数量，数组是无序且有重复的

POJ1811

在这里插入图片描述
题意：
输入一个t，之后输入t个数字，判断每个数字是不是质数，如果是质数输出Prime，否则输出这个数的最小的一个质因子。
分析：
利用Miller_Rabin质数判定和Pollard_rho质因数分解即可。模板题
AC代码：

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <time.h>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll Mod = 1000000007;
const int maxn = 1000000 + 10;
#define INF 0x3f3f3f3f
#define eps 10e-10

// Miller_Rabin 算法进行素数测试
//速度快，而且可以判断 <2^63的数
const int S = 20;//随机算法判定次数，S越大，判错概率越小

//计算 (a*b)%c.   a,b都是long long的数，直接相乘可能溢出的
ll Mult_mod (ll a,ll b,ll c)  //减法实现比取模速度快
{
    //返回(a*b) mod c,a,b,c<2^63
    a%=c;
    b%=c;
    ll ret=0;
    while (b)
    {
        if (b&1)
        {
            ret+=a;
            if (ret>=c) ret-=c;
        }
        a<<=1;
        if (a>=c) a-=c;
        b>>=1;
    }
    return ret;
}

//计算  x^n %c(快速幂)
ll Pow_mod (ll x,ll n,ll mod)
{
    if (n==1) return x%mod;
    x%=mod;
    ll tmp=x;
    ll ret=1;
    while (n)
    {
        if (n&1) ret=Mult_mod(ret,tmp,mod);
        tmp=Mult_mod(tmp,tmp,mod);
        n>>=1;
    }
    return ret;
}

//以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
//一定是合数返回true,不一定返回false
bool Check (ll a,ll n,ll x,ll t)
{
    ll ret=Pow_mod(a,x,n);
    ll last=ret;
    for (int i=1; i<=t; i++)
    {
        ret=Mult_mod(ret,ret,n);
        if(ret==1&&last!=1&&last!=n-1) return true; //合数
        last=ret;
    }
    if (ret!=1) return true;
    return false;
}

// Miller_Rabin()算法素数判定 是素数返回true.(可能是伪素数，但概率极小)
bool Miller_Rabin (ll n)
{
    if (n<2) return false;
    if (n==2) return true;
    if ((n&1)==0) return false;//偶数
    ll x=n-1;
    ll t=0;
    while ((x&1)==0)
    {
        x>>=1;
        t++;
    }
    for (int i=0; i<S; i++)
    {
        ll a=rand()%(n-1)+1;
        if (Check(a,n,x,t))
            return false;
    }
    return true;
}



//pollard_rho 算法进行质因数分解
ll factor[100];//质因数分解结果（刚返回时是无序的）
int tol;//质因数的个数。数组下标从0开始

ll Gcd (ll a,ll b)
{
    if (a==0) return 1;  //???????
    if (a<0) return Gcd(-a,b);
    while (b)
    {
        ll t=a%b;
        a=b;
        b=t;
    }
    return a;
}

ll Pollard_rho (ll x,ll c)
{
    ll i=1,k=2;
    ll x0=rand()%x;
    ll y=x0;
    while (true)
    {
        i++;
        x0=(Mult_mod(x0,x0,x)+c)%x;
        ll d=Gcd(y-x0,x);
        if (d!=1 && d!=x) return d;
        if (y==x0) return x;
        if (i==k)
        {
            y=x0;
            k+=k;
        }
    }
}

//对n进行素因子分解
void Findfac (ll n)
{
    if (Miller_Rabin(n)) //素数
    {
        factor[tol++]=n;
        return;
    }
    ll p=n;
    while (p>=n) p=Pollard_rho(p,rand()%(n-1)+1);
    Findfac(p);
    Findfac(n/p);
}

int main ()
{
    //Miller_Rabin(x)返回true代表x是素数
    //Findfac(n)对n进行质因数分解，结果保存在数组factor中下标从0开始用，tol是数量，数组是无序且有重复的
    int t;
    scanf("%d", &t);
    while (t--)
    {
        ll n;
        scanf("%lld", &n);
        if (Miller_Rabin(n))
        {
            printf("Prime\n");
            continue;
        }
        tol = 0;
        Findfac(n);
        ll ans = factor[0];
        for (int i = 1; i < tol; i++)
            if (factor[i] < ans)
                ans = factor[i];
        printf("%lld\n",ans);
    }
    return 0;
}

2022 CCPC网络赛H Mutiple Set

img
img
img
没找到补题地址，不敢保证代码正确性

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

//****************************************************************
// Miller_Rabin 算法进行素数测试
//速度快，而且可以判断 <2^63的数
//****************************************************************
const int S=20;//随机算法判定次数，S越大，判错概率越小

ll Mult_mod (ll a,ll b,ll c)  //减法实现比取模速度快
{
    //返回(a*b) mod c,a,b,c<2^63
    a%=c;
    b%=c;
    ll ret=0;
    while (b)
    {
        if (b&1)
        {
            ret+=a;
            if (ret>=c) ret-=c;
        }
        a<<=1;
        if (a>=c) a-=c;
        b>>=1;
    }
    return ret;
}

//计算  x^n %c
ll Pow_mod (ll x,ll n,ll mod) //x^n%c
{
    if (n==1) return x%mod;
    x%=mod;
    ll tmp=x;
    ll ret=1;
    while (n)
    {
        if (n&1) ret=Mult_mod(ret,tmp,mod);
        tmp=Mult_mod(tmp,tmp,mod);
        n>>=1;
    }
    return ret;
}

//以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
//一定是合数返回true,不一定返回false
bool Check (ll a,ll n,ll x,ll t)
{
    ll ret=Pow_mod(a,x,n);
    ll last=ret;
    for (int i=1; i<=t; i++)
    {
        ret=Mult_mod(ret,ret,n);
        if(ret==1&&last!=1&&last!=n-1) return true; //合数
        last=ret;
    }
    if (ret!=1) return true;
    return false;
}

// Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数，但概率极小)
//合数返回false;

bool Miller_Rabin (ll n)
{
    if (n<2) return false;
    if (n==2) return true;
    if ((n&1)==0) return false;//偶数
    ll x=n-1;
    ll t=0;
    while ((x&1)==0)
    {
        x>>=1;
        t++;
    }
    for (int i=0; i<S; i++)
    {
        ll a=rand()%(n-1)+1; //rand()需要stdlib.h头文件
        if (Check(a,n,x,t))
            return false;//合数
    }
    return true;
}


//************************************************
//pollard_rho 算法进行质因数分解
//************************************************

ll factor[100];//质因数分解结果（刚返回时是无序的）
int num[100];
int tot;//质因数的个数。数组下标从0开始
int sum;
set<ll> st;
set<ll>::iterator it;
ll tmp;
ll L, R, K;
ll l, r;
ll bas[60];
ll ans[1000005];

ll Gcd (ll a,ll b)
{
    if (a==0) return 1;  //???????
    if (a<0) return Gcd(-a,b);
    while (b)
    {
        ll t=a%b;
        a=b;
        b=t;
    }
    return a;
}

ll Pollard_rho (ll x,ll c)
{
    ll i=1,k=2;
    ll x0=rand()%x;
    ll y=x0;
    while (true)
    {
        i++;
        x0=(Mult_mod(x0,x0,x)+c)%x;
        ll d=Gcd(y-x0,x);
        if (d!=1 && d!=x) return d;
        if (y==x0) return x;
        if (i==k)
        {
            y=x0;
            k+=k;
        }
    }
}
//对n进行素因子分解
void Findfac (ll n)
{
    if (Miller_Rabin(n)) //素数
    {
        st.insert(n);
        return;
    }
    ll p=n;
    while (p>=n) p=Pollard_rho(p,rand()%(n-1)+1);
    Findfac(p);
    Findfac(n/p);
}

bool judge(ll x)
{
    l = (L + x - 1) / x;
    r = R / x;

    //cout << l << ' ' << r << '\n';
    tmp = K;

    if(r - l - 1 >= 48) return false;

    if(r == l) tmp = 2ll * tmp;
    else if(r + 1 == l) tmp = 4ll * tmp;
    else
    {
        if(tmp % bas[r - l - 1] == 0) tmp /= bas[r - l - 1];
        else return false;
    }

    if(tmp % (x * (l + r)) == 0)
    {
        tmp /= x * (l + r);
        if(tmp == r - l + 1) return true;
        else return false;
    }
    else return false;

}

void dfs(ll x, int cnt)
{
    if(cnt == tot + 1)
    {
        //cout << x << '\n';
        if(judge(x)) ans[++sum] = x;
        //if(x == 15008622) cout << "kkk" << '\n';
    }
    else
    {
        ll temp = 1ll;
        for(int i = 0; i <= num[cnt]; ++i)
        {
            dfs(x * temp, cnt + 1);
            temp *= factor[cnt];
        }
    }
}

void init()
{
    bas[0] = 1;
    for(int i = 1; i <= 50; ++i) bas[i] = bas[i - 1] * 2ll;
}

int main ()
{
    init();

    //cout << judge(25) << '\n';

    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%lld%lld%lld", &L, &R, &K);

        //cout << judge(28) << '\n';

        if (Miller_Rabin(K))
        {
            if(L <= K && K <= R && 2 * K > R) printf("1\n%lld\n", K);
            else printf("No Solution\n");
            continue;
        }

        //cout << 5 << '\n';

        sum = tot = 0;
        st.clear();
        Findfac(K);

        for(it = st.begin(); it != st.end(); ++it)
        {
            factor[++tot] = *it;
            num[tot] = 0;
            tmp = K;
            while(tmp % factor[tot] == 0)
            {
                ++num[tot];
                tmp /= factor[tot];
            }
            //cout << tot << ' ' << factor[tot] << ' ' << num[tot] << '\n';
        }

//        cout << 5 << '\n';

        dfs(1, 1);

        //cout << 5 << '\n';

        if(sum >= 100000) printf("Too Many!\n");
        else if(sum == 0) printf("No Solution\n");
        else
        {
            printf("%d\n", sum);
            sort(ans + 1, ans + sum + 1);
            for(int i = 1; i <= sum; ++i) printf("%lld ", ans[i]);
            putchar('\n');
        }

    }
    return 0;
}