0%

数论笔记

主要是写给自己看的,所以写的很简洁,很多东西也是直接复制其他博客、资料的,谨慎参考。

逆元

$a$ 的逆元,即为满足 $a\times a^{-1}\equiv 1 \pmod{p}$ 的 $a^{-1}$。

扩展欧几里得求逆元

可以用扩展欧几里得算法求出 $a$ 的逆元,同时根据裴蜀定理,我们又能知道若 $\gcd(a,p)\neq 1$,则 $a$ 不存在逆元。

费马小定理求逆元

更简单的求逆元方法则是利用费马小定理。

费马小定理: 若 $p$ 为质数,$a$ 为正整数,且 $\gcd(a,p)=1$,则 $a^{p-1}\equiv 1 \pmod{p}$

$a^{-1}\equiv a^{p-2} \pmod{p}$,因此可以直接快速幂求。

线性求逆元

要求 $1\dots n$ 的逆元,我们有更快的方法。

考虑带余除法,$a\bmod b = a - \lfloor \dfrac{a}{b}\rfloor \times b$,

则 $a\bmod b = -\lfloor \dfrac{a}{b}\rfloor \times b \pmod{a}$

两边同乘 $b^{-1}\times (a \bmod b)^{-1}$,得

$b^{-1} = -\lfloor \dfrac{a}{b}\rfloor \times (a \bmod b)^{-1} \pmod{a}$

由于 $a \bmod b$ 小于 $b$ ,因此可以递推求解。

1
2
3
4
5
6
void inverse()
{
inv[1] = 1;
for (int i = 2; i <= n; i++)
inv[i] = (p - p / i) * inv[p % i] % p;
}

线性求阶乘的逆元

可以先用费马小定理求出 $n!$ 的逆元,然后从 $n$ 乘到 $1$ 能够得到所有 $(i!)^{-1}$,

线性求任意$n$个数的逆元

与求阶乘逆元的原理类似。求出 $a_i$ 的前缀积 $s_i$,用费马小定理或扩欧能够求出 $s_n^{-1}$,进而求出 $s_i^{-1}(1 \leq i \leq n)$,则 $a_i^{-1}=s_{i}^{-1}\times s_{i-1}$


欧拉函数

欧拉函数 $\varphi(n)$,表示 $1\dots n$ 中与 $n$ 互质的数的个数。它有很多神奇的性质。

设 $n=\prod_{i=1}^{s} p_i^{k_i}$,$p_i$ 是质数,那么 $\varphi(n)=n\times \prod_{i=1}^{s}\dfrac{p_i-1}{p_i}$

证明

引理: 若 $x=p^k$,那么 $\varphi(x)=p^{k-1}\times(p-1)$

证明:当 $y \bmod p \neq 0$ 时,$x \perp y$。我们将 $x$ 划分为 长度为 $p$ 的 $p^{k-1}$ 段,每一段都有 $p-1$ 个数与 $x$ 互质,因此 $\varphi(x)=p^{k-1}\times(p-1)$。

欧拉函数的一些性质

  • 欧拉函数是积性函数,即对于$\gcd(a,b)=1$,$\varphi(ab)=\varphi(a)\times \varphi(b)$

特别的,当 $n$ 是奇数时,$\varphi(2n)=\varphi(n)$

  • $n=\sum_{d|n}\varphi(d)$

证明:如果 $\gcd(k,n)=d$,那么 $\gcd(\frac{k}{d}, \frac{n}{d})=1(k \leq n)$.

如果我们设 $f(x)$ 表示 $\gcd(k,n)=x$ 的数的个数,那么 $n=\sum_{i=1}^{n}f(i)$。

根据上面的证明,我们发现,$f(x)=\varphi(\dfrac{n}{x})$,从而 $n=\sum_{d|n}\varphi(\dfrac{n}{d})$。

注意到约数 $n$ 和 $\dfrac{n}{d}$ 具有对称性,因此上式化为 $n=\sum_{d|n}\varphi(d)$

  • $1$ 到 $n$ 中与 $n(n>1)$ 互质的数的和为 $\dfrac{n\times \varphi(n)}{2}$。

埃筛/欧拉筛

埃筛求区间内质数个数

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
const int N = 1e6 + 5;

bool prime1[N], prime2[N];
LL prime[N];
int cnt;

// [a, b)
void init(LL a, LL b)
{
// [2, sqrt(b)) --> 1
for (LL i = 2; i * i < b; i++) prime1[i] = 1;
// [a, b) --> 1
for (LL i = 0; i < b - a; i++) prime2[i] = 1;
for (LL i = 2; i * i < b; i++)
if (prime1[i])
{
for (LL j = i * 2; j * j < b; j += i)
prime1[j] = 0;
// (a + i - 1) / i * i 最接近 a 的 i 的倍数
for (LL j = max(2LL, (a + i - 1) / i) * i; j < b; j += i)
prime[j - a] = 0;
}
for (LL i = 0; i < b - a; i++)
if (prime2[i]) prime[++cnt] = i + a;
}

线性筛质数

设 $pr_i$ 表示 $i$ 的最小质因子。枚举所有不超过 $pr_i$ 的质数 $p$,使 $pr_(i\cdot p) = p$,相当于将每个数的质因子降序分解,每个数只会被它的最小质因子筛一次,因此复杂度是 $O(n)$ 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Shaker(int x)
{
for (int i = 2; i <= x; i++)
{
if (!pr[i]) prime[++cnt] = pr[i] = i;
for (int j = 1; j <= cnt; j++)
{
int k = i * prime[j];
if (k > x) break;
pr[k] = prime[j];
if (i % prime[j] == 0) break;
}
}
}

欧拉定理

欧拉定理

若 $\gcd(a, m) = 1$,则 $a^{\varphi(m)} \equiv 1 \pmod{p}$

证明:

证明十分简单。

简化剩余系:$m$ 的完全剩余系中与 $m$ 互素的数构成的子集

设 $r_1, r_2, \cdots, r_{\varphi(m)}$ 为模 $m$ 意义下的一个简化剩余系,则 $ar_1, ar_2, \cdots, ar_{\varphi(m)}$ 也为模 $m$ 意义下的一个简化剩余系。所以 $r_1r_2\cdots r_{\varphi(m)} \equiv ar_1\cdot ar_2\cdots r_{\varphi(m)} \equiv a^{\varphi(m)}r_1r_2\cdots r_{\varphi(m)} \pmod{m}$,可约去 $r_1r_2\cdots r_{\varphi(m)}$,即得到 $a^{\varphi(m)} \equiv 1 \pmod{m}$。

扩展欧拉定理

Code

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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int M = 1000000 + 5;
const int N = 20000000 + 5;

char s[N];
LL a, b, m;
int pr[M], prime[M], phi[M], cnt;

void init()
{
pr[1] = 1, phi[1] = 1;
for (int i = 2; i <= m; i++)
{
if (!pr[i]) prime[++cnt] = i, pr[i] = i, phi[i] = i - 1;
for (int j = 1; j <= cnt; j++)
{
int k = i * prime[j];
if (k > m) break;
pr[k] = prime[j];
if (i % prime[j] == 0)
{
phi[k] = phi[i] * prime[j];
break;
}
else phi[k] = phi[i] * (prime[j] - 1);
}
}
}

LL qpow(LL a, LL b, LL p)
{
LL res = 1;
for (; b; b >>= 1, a = a * a % p)
if (b & 1) res = res * a % p;
return res;
}

int main()
{
scanf("%lld%lld%s", &a, &m, s);
init();
int len = strlen(s), flag = 0;
for (int i = 0; i < len; i++)
{
b = (b << 3) + (b << 1) + s[i] - '0';
if (b >= phi[m]) flag = 1;
b %= phi[m];
}
printf("%lld\n", qpow(a, flag ? b + phi[m] : b, m));
return 0;
}

中国剩余定理

模数互质的中国剩余定理

中国剩余定理(CRT)可求解如下形式一元线性同余方程组。

令 $M=m_1m_2\cdots m_n$,$M_i=\frac{M}{m_i}$,$M_i$ 在模 $m_i$ 意义下的逆元为 ${M_i}^{-1}$,则方程租的唯一解为 $x\equiv \sum_{i=1}^{n} a_iM_iM_i^{-1} \pmod M$。

由于 $M_i(M_i^{-1} \bmod m_i) \equiv 1 \pmod {m_i}$,$M_i(M_i^{-1} \bmod m_i) \equiv 0 \pmod {m_j} (j \neq i)$,因此 CRT 是正确的。

模数不互质的扩展中国剩余定理

两个方程

设两个方程分别是 $x\equiv a_1 \pmod {m_1}$、$x\equiv a_2 \pmod {m_2}$;

将它们转化为不定方程:$x=m_1p+a_1=m_2q+a_2$,其中 $p, q$ 是整数,则有 $m_1p-m_2q=a_2-a_1$。

由裴蜀定理,当 $a_2-a_1$ 不能被 $\gcd(m_1,m_2)$ 整除时,无解;

其他情况下,可以通过扩展欧几里得算法解出来一组可行解 $(p, q)$;

则原来的两方程组成的模方程组的解为 $x\equiv b\pmod M$,其中 $b=m_1p+a_1$,$M=\text{lcm}(m_1, m_2)$。

多个方程

用上面的方法两两合并就可以了……

Code
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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100000 + 5;

int n;
LL a[N], b[N];

__int128 gcd(__int128 a, __int128 b)
{
return b == 0 ? a : gcd(b, a % b);
}

void exgcd(__int128 a, __int128 b, __int128 &x, __int128 &y)
{
if (b == 0)
{
x = 1, y = 0;
return;
}
LL q = a / b, r = a % b;
exgcd(b, r, y, x);
y -= q * x;
}

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
__int128 A = a[1], B = b[1];
__int128 d, x, y, mod;
for (int i = 2; i <= n; i++)
{
d = gcd(A, a[i]);
if ((b[i] - B) % d != 0)
{
puts("-1");
return 0;
}
exgcd(A, a[i], x, y);
mod = a[i] / d;
x = ((b[i] - B) / d % mod * x % mod + mod) % mod;
B = A * x + B;
A = a[i] / d * A;
B %= A;
}
cout << (LL)B << endl;
return 0;
}

Lucas 定理

Lucas 定理

Lucas 定理:对于质数 $p$,有

$n\bmod p$ 和 $m\bmod p$ 一定小于 $p$,可以直接求解,$\displaystyle\binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}$ 可以继续用 Lucas 定理求解。这也就要求 $p$ 的范围不能够太大,一般在 $10^5$ 左右。边界条件:当 $m=0$ 的时候,返回 $1$。

时间复杂度为 $O(f(p) + g(n)\log n)$ ,其中 $f(n)$ 为预处理组合数的复杂度, $g(n)$ 为单次求组合数的复杂度。

1
2
3
4
5
6
7
8
9
10
11
LL C(int n, int m)
{
if (m > n) return 0;
return fact[n] * inv(fact[m], mod) % mod * inv(fact[n - m], mod) % mod;
}

LL Lucas(int n, int m)
{
if (m == 0) return 1;
return Lucas(n / mod, m / mod) * C(n % mod, m % mod) % mod;
}

扩展 Lucas 定理


BSGS

BSGS 算法

BSGS 算法可以求解形如 $A^x\equiv B \pmod C$ 的解的问题,即离散对数问题。

由指数模的周期性,$A^x\equiv B \pmod C$ 有解当且仅当其在 $0 \leq x \le C$ 内存在解。

BSGS 算法适用于 $\gcd(A, C)=1$ 的情况。将 $0\dots C-1$ 分成 $n$ 组,每组有 $m = \frac{C}{n}$ 个数,对每组进行询问 $A^{im-y} \equiv B \pmod C$,$1\leq i\leq n, 0\leq y \le m$。移项后得到 $A^{im} \equiv A^yB \pmod C$。因此我们枚举 $0\dots m-1$ 将所有 $A^yB\bmod C$ 存入哈希表中,再枚举计算 $A^{im}$ 的值在哈希表中查询,进而得出解。复杂度为$O(\sqrt C)$。

扩展 BSGS 算法

当 $\gcd(A, C)$ 不等于一时,$A$ 关于模 $C$ 的逆元不存在。此时应该把 $A, C$ 处理成互质。

将 $A^x\equiv B \pmod C$ 看做 $A^x+Cy=B$。将方程同除 $d_1=\gcd(A,C)$,得到 $B_1=\frac{A}{d_1}A^{x-1}+C_1y$,有可能 $A$ 和 $C_1$ 仍然不互素,一直这样做下去,直到 $A$ 和 $C_i$ 互素。在这个过程中,如果 $B_i$ 不被 $\gcd(A, C_i)$ 整除则无解。

最终得到 $B_n = \frac{A_n}{d_1d_2\cdots d_n}A^{x-n}+ C_{n}y$,记 $D=\frac{A^n}{d_1d_2\cdots d_n}$,$\gcd(D, C_n)=1$,因此式子变为 $A^{x-n}\equiv B_nD^{-1} \pmod {C_n}$,此时便能求解了。

Code

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long LL;
LL X, Y, Z, K;

LL gcd(LL a, LL b)
{
return b == 0 ? a : gcd(b, a % b);
}

void exgcd(LL a, LL b, LL &x, LL &y)
{
if (b == 0)
{
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}

LL inv(LL a, LL p)
{
LL x, y;
exgcd(a, p, x, y);
return (x % p + p) % p;
}

namespace Hash
{
const int N = 50000;
const int H = 999979;
int tot, head[H], nxt[N];
LL num[N], val[N];

void init()
{
tot = 0;
memset(head, 0, sizeof(head));
}
void Insert(int x, int y)
{
int h = x % H;
for (int e = head[h]; e; e = nxt[e])
if (num[e] == x)
{
val[e] = y;
return;
}
nxt[++tot] = head[h], head[h] = tot;
num[tot] = x, val[tot] = y;
}
LL Query(LL x)
{
int h = x % H;
for (int e = head[h]; e; e = nxt[e])
if (num[e] == x) return val[e];
return -1;
}
}

LL BSGS(LL a, LL b, LL c)
{
int cnt = 0;
LL g, d = 1;
while ((g = gcd(a, c)) != 1)
{
if (b % g != 0) return -1;
cnt++, b /= g, c /= g;
d = d * (a / g) % c;
}
b = b * inv(d, c) % c;

Hash::init();
LL s = ceil(sqrt(c)), p = 1;
for (int i = 0; i < s; i++)
{
if (p == b) return i + cnt;
Hash::Insert(p * b % c, i);
p = p * a % c;
}

LL q = p, t;
for (int i = s; i - s + 1 <= c - 1; i += s)
{
t = Hash::Query(q);
if (t != -1) return i - t + cnt;
q = q * p % c;
}
return -1;
}

bool check()
{
for (int i = 0, j = 1; i <= 10; i++)
{
if (j == K)
{
printf("%d\n", i);
return true;
}
j = 1LL * j * X % Z;
}
if (X == 0)
{
puts("No Solution");
return true;
}
return false;
}

int main()
{
while (scanf("%lld%lld%lld", &X, &Z, &K), X + Z + K > 0)
{
X %= Z, K %= Z;
if (check()) continue;
LL ans = BSGS(X, K, Z);
if (ans == -1) puts("No Solution");
else printf("%lld\n", ans);
}
return 0;
}

原根

设 $n>1$,$(a, n)=1$,则必有 $r(1\leq r\leq n)$ 使得 $a^r\equiv 1 \pmod n$。满足 $a^r\equiv 1 \pmod n$ 的最小整数
$r$ 称为 $a$ 模 $n$ 的阶,记为 $Ord_n{a}$。

只有当 $(a, n)=1$ 时才有阶。

阶的性质:

(1) 若 $a^N \equiv 1 \pmod n$,则 $r\mid N$;

(2) $r\mid \varphi(n)$。特别的,若 $n$ 是素数 $p$,则 $r\mid p-1$。

原根

定义

若 $a$ 模 $m$ 的阶等于 $\varphi(m)$,则称 $a$ 为模 $m$ 的一个原根。

显然,原根与 $m$ 互质。

性质

设 $r=Ord_m(a)$,则 $a^0, a^1, \cdots, a^{r-1}$ 构成模 $m$ 的简化剩余系,反之亦然。

求所有原根

设 $g$ 为 $m$ 的一个原根,则集合 $S = \{g^s \mid 1 \leq s \leq \varphi(m), (s, \varphi(m)) = 1\}$ 给出 $m$ 的全部原根。因此,若 $m$ 有原根,则 $m$ 有 $\varphi(\varphi(m))$ 个关于模 $m$ 两两互不同余的原根。

求质数 p 的原根

原根的分布比较广,并且最小的原根通常也较小,因此可以从小到大枚举正整数快速寻找一个原根。对于一个质数 $p$,对于 $p-1$ 的每一个质因子 $a$,检查 $g^\frac{p-1}{a}\equiv 1\pmod p$ 是否成立,若成立则说明 $g$ 不是原根。

N 次剩余

二次剩余

二次剩余:解 $x^2\equiv n \pmod p$,$p$ 是奇素数。

解的数量

一个方程对应两个解,且互为相反数。

二次剩余的个数恰为 $\frac{p-1}{2}$,非二次剩余的个数也为 $\frac{p-1}{2}$。

欧拉准则

勒让德符号:

欧拉准则:$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p$

Cipolla 算法

随机一个 $a$,使得 $\left(\frac{a^2-n}{p}\right) = -1$,令 $w=\sqrt {a^2-n}$,即 $w$ 不是二次剩余,则 $x=(a+w)^{\frac{p+1}{2}}$ 是 $x^2\equiv n\pmod p$ 的解。

这里的 $w$ 是一个新的数域,类似虚数。

证明:

首先有一些东西:

$\omega^p\equiv -\omega\pmod p$

证明:$\omega^p\equiv \omega\times\omega^{p-1}\equiv\omega\times(\omega^2)^{\frac{p-1}{2}}\equiv\omega\times\left(a^2-n\right)^{\frac{p-1}{2}}\equiv-\omega\pmod p$

$(a+b)^n\equiv a^n+b^n\pmod n(n\in P)$

用二项式定理不难证明。

于是,

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
#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL n, p, w;

inline LL qpow(LL a, LL b)
{
LL res = 1;
for (; b; b >>= 1, a = a * a % p)
if (b & 1) res = res * a % p;
return res;
}

inline LL ch(LL x)
{
return (x % p + p) % p;
}

struct Node
{
LL a, b;
Node(LL a = 0, LL b = 0) : a(a), b(b) {}
Node operator * (const Node &x) const
{
return Node(ch(a * x.a % p + b * x.b % p * w % p), ch(a * x.b % p + b * x.a % p));
}
};

inline LL qpowx(Node a, LL b)
{
Node res(1, 0);
for (; b; b >>= 1, a = a * a)
if (b & 1) res = res * a;
return res.a;
}

inline LL Cipolla(LL n, LL p)
{
if (n == 0) return 0;
if (qpow(n, (p - 1) >> 1) == p - 1) return -1;
while (true)
{
LL a = rand();
w = ch(a * a % p - n);
if (qpow(w, (p - 1) >> 1) == p - 1) return qpowx(Node(a, 1), (p + 1) >> 1);
}
}

int main()
{
srand(time(NULL));
int T;
scanf("%d", &T);
while (T--)
{
scanf("%lld%lld", &n, &p);
LL ans1 = Cipolla(n, p), ans2 = ch(p - ans1);
if (ans1 > ans2) swap(ans1, ans2);
if (ans1 == -1) puts("Hola!");
else if (ans1 == ans2) printf("%lld\n", ans1);
else printf("%lld %lld\n", ans1, ans2);
}
return 0;
}