多校联赛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的模等于a
b的逆元的模;
逆元就是这样应用的。

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

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)*1+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;
}
}
}

推导:

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

Q!(modp)=(p1)!(modp)(Q+1)×(Q+2)××(p1)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