多校联赛3补题

, ,
暴零现场。。。。

2019-07-29

1 Fansblog

这题真的让我发现自己有好多知识盲区 这么菜怎么不去死

知识点：

  • 威尔逊定理

$(p−1)!≡p−1≡−1 (mod p) $(p is a prime)

* 质数的密度分布

数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系.

  • 逆元:

什么是逆元
当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：
设c是b的逆元，则有bc≡1(mod m)；
则(a/b)%m = (a/b)1%m = (a/b)bc%m = ac(mod m);
即a/b的模等于ab的逆元的模；
逆元就是这样应用的。

逆元的求法有很多
这里用到的是阶乘的逆元

1
2
3
4
5
6
7
8
fac[0] = fac[1] = 1;

for(int i = 2; i <= MAXN; i++)fac[i] = fac[i - 1] * i % mod;

inv[MAXN] = quipow(fac[MAXN], mod - 2);

for(int i = MAXN - 1; i >= 0; i--)inv[i] = inv[i + 1] * (i + 1) % mod;

  • 二分乘法：

由于计算机底层设计的原因，做加法往往比乘法快的多，因此将乘法转换为加法计算将会大大提高（大
数，比较小的数也没必要）乘法运算的速度，除此之外，当我们计算a*b%mod的时候，往往较大的数计算a＊b会超出long long int的范围，这个时候使用快速乘法方法也能解决上述问题．
　　快速乘法的原理就是利用乘法分配率来将a＊b转化为多个式子相加的形式求解（注意这时使用乘法分配 率的时候后面的一个乘数转化为二进制的形式计算）．举个栗子
　　20＊14　＝　20＊(1110)2 = 20＊(2^3)＊1 + 20＊(22)＊1+20＊(21)＊１+20＊(2^0)＊0 = 160+80+40=280.

1
2
3
4
5
6
7
8
9
10
11
12
ll mul(ll a, ll b)
{
    ll res = 0;
    while (b)
    {
        if (b & 1)
            res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res % mod;
}
  • 快速幂：

与快乘异曲同工

1
2
3
4
5
6
7
8
9
10
11
12
13
ll mod_pow(ll x, ll n, ll mod)
{
    ll res = 1;
    while (n)
    {
        if (n & 1)
            res = (res * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return res;
}

  • 埃氏素数筛算法：
    看图就好
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
bool isprime(ll a)
{
    for (int i = 2; i * i <= a; i++)
    {
        if (a % i == 0)
        {
            return false;
        }
    }
    return true;
}

void getprime()//埃拉托色尼筛法
{
    for (int i = 2; i <= maxn; i++)
    {
        if (!vis[i])//非零为素数
        {
            prime[cnt++] = i;
        }
        for (int j = 0; j < cnt && (ll)i * prime[j] <= maxn; j++)
        {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}

推导：

由威尔逊：(p−1)!modp=−1(p - 1)!mod p = -1,即(p−1)!modp=p−1(p - 1)!mod p = p - 1
所以

Q!(modp)=(p−1)!(modp)(Q+1)×(Q+2)×…×(p−1)Q!(mod p)=\frac{(p-1)!(modp)}{(Q+1)\times(Q+2)\times\ldots\times(p-1)}

步骤：

因为两个素数之间的间隔不会超过300,我们从P-1开始一个个查验找Q。再把（P-1）乘上[Q,P-1]的逆元即可。注意因为数很大，所有涉及乘的地方都要用快速乘。

代码实现：

  • 第一种
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
/*************************************************************************
 > FileName:
 > Author:      huangchangsheng
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int INF = 0x3f3f3f3f;            //int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1e7 + 10;
ll mod;
int prime[maxn + 10], cnt;
bool vis[maxn + 10];

bool isprime(ll x)
{
    for (int i = 0; i < cnt && (ll)prime[i] * prime[i] <= x; i++)
        if (x % prime[i] == 0)
            return 0;
    return 1;
}

bool isprime(ll a)
{
    for (int i = 2; i * i <= a; i++)
    {
        if (a % i == 0)
        {
            return false;
        }
    }
    return true;
}

void getprime()//埃拉托色尼筛法
{
    for (int i = 2; i <= maxn; i++)
    {
        if (!vis[i])//非零为素数
        {
            prime[cnt++] = i;
        }
        for (int j = 0; j < cnt && (ll)i * prime[j] <= maxn; j++)
        {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}
ll mul(ll a, ll b)
{
    ll res = 0;
    while (b)
    {
        if (b & 1)
            res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res % mod;
}

ll qpow(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = mul(res, a);
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}

int main()
{
    int t;
    getprime();
    ll p, q;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%lld", &p);
        mod = p;
        q = p - 1;
        while (!isprime(q))
            q--;
        ll ans = p - 1;
        for(ll i = q + 1; i <= p - 1; i++)
            ans = mul(ans, qpow(i, mod - 2));
        printf("%lld\n", ans);
    }
    return 0;
}

  • 第二种
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
/*************************************************************************
 > FileName:
 > Author:      huangchangsheng
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
//(p-2)!=1(mod p)
//(p-3)!=1*(p-2)^(p-2)(mod p)
//(p-4)!=1*(p-2)^(p-2)*(p-3)^(p-2)(mod p)
 ************************************************************************/
#include<iostream>
#include<iomanip>
#include<cmath>
#include<map>
#include<string>
#include<vector>
#include<set>
#include<algorithm>
#include<string.h>
using namespace std;
typedef unsigned long long ll;
ll P;
unsigned long long kuai(__int128 a, __int128 b) //快速幂
{
    __int128 sum = 1;
    a = a % P;
    while(b > 0)
    {
        if(b % 2 == 0)
        {
            a = (a * a) % P;
            b = b / 2;
        }
        else
        {
            sum = (sum * a) % P;
            a = (a * a) % P;
            b = b / 2;
        }
    }
    return sum;
}
bool prime( long long a)//
{
    for(int i = 2; i <= sqrt(a); i++)
    {
        if(a % i == 0)
            return false;
    }
    return true;
}
int main()
{
    int T;
    __int128 Q, ans;
    scanf("%d", &T);
    while(T--)
    {
        cin >> P;
        Q = P - 2;
        ans = 1;
        for(int i = 2; !prime(Q); Q--, i++)
        {
            ans = (ans * kuai(P - i, P - 2)) % P;
        }
        cout << (ll)ans << endl;
    }
}

参考博客

2 Find the answer