感谢@Cute_SilverWolf为这篇文章作出的贡献。

写这篇文章是因为这四节课题目看似很少，内容是真多。在几个月前我就复习过一次这俩东西但是没写笔记现在又忘完了，于是趁自己有时间复习提高组就赶紧写了。

数论部分

整除

对于两个整数aa，bb，存在两个唯一的整数qq，rr满足：

b=aq+r(0≤r≤∣a∣)b = aq + r \left ( 0 \leq r \leq \left | a \right | \right )

当r=0r=0，我们就说aa整除bb，记作a∣ba | b。

整除的基本性质

  • a∣c,b∣c,(a,b)=1⇒ab∣ca|c, b|c, \left ( a, b \right ) = 1 \Rightarrow ab|c

  • a∣bc,(a,b)=1⇒a∣ca|bc, \left ( a, b \right ) = 1 \Rightarrow a|c

  • p∣ab⇒p∣ap|ab \Rightarrow p|a或p∣bp|b

公约数公倍数

  • (a,b)=(a,a+b)=(a,a−b)=(a,a mod b)\left ( a, b \right ) = \left ( a, a + b \right ) = \left ( a, a - b \right ) = \left ( a, a \bmod b \right )

  • (ac,bc)=c(a,b)\left ( ac, bc \right ) = c\left ( a, b \right )

  • (a,b)×[a,b]=ab\left ( a, b \right ) \times \left [ a, b \right ] = ab

神秘结论

  • 1∼n1 \sim n的所有数约数个数一共是O(nlog⁡n)O \left ( n \log n \right )

  • 1∼n1 \sim n素数个数O(nln⁡n)\displaystyle O \left ( \frac{n}{\ln n} \right )个

欧几里得算法 gcd

前面我们知道，(a,b)=(a,a mod b)\left ( a, b \right ) = \left ( a, a \bmod b \right )，所以可以写出下面的代码求解gcd：

1
2
3
4
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

裴蜀定理

设a,ba,b不全为00。

∃x,y\exist x, y使得ax+by=gcd⁡(a,b)ax + by = \gcd(a,b)

不失一般性，设0<a≤b0 < a \leq b。

下面对aa的两种情况进行讨论：

  • a=0a=0，令x=0,y=1x=0,y=1满足条件。

  • a>0a>0，则令c=b mod a=b−akc=b \bmod a = b - ak。

所以我们可以尝试找到x0，y0x_0，y_0满足cx0+ay0=gcd⁡(c,a)cx_0+ay_0=\gcd(c,a)。

所以:

gcd⁡(a,b)=gcd(c,a)=(b−ak)x0+ay0=(y0−x0k)a+x0b\gcd(a, b) = gcd(c, a) = (b - ak)x_0 + ay_0 = (y_0 - x_0 k)a+x_0b

所以原方程的x=y0−x0kx=y_0-x_0k，y=x0y=x_0。

扩展欧几里得算法 exgcd

就是利用到我们刚刚提到的裴蜀定理：

1
2
3
4
5
6
7
8
9
10
11
int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

代码源OJ 488 - 扩展欧几里得2

题目描述

多测，给你三个整数a,b,da,b,d，输出ax+by=dax+by=d的最小非负整数解(x,y)\left ( x, y \right )。如果无解输出−1-1，否则输出xx最小的解。

对于100%100 \%的数据，1≤T≤1041 \leq T \leq 10^4，1≤a,b≤1091 \leq a,b \leq 10^9，1≤d≤10181 \leq d \leq 10^{18}。

思路

令gg为gcd⁡(a,b)\gcd(a,b)，且x0,y0x_0,y_0为ax0+by0=gax_0 + by_0 = g的一组解。

首先如果dd无法整除gg，原方程无解。

否则x=x0×(dg),y=y0×(dg)x=x_0 \times \left ( \displaystyle \frac{d}{g} \right ),y=y_0 \times \left ( \displaystyle \frac{d}{g} \right )就是原方程的一组解。我们可以求出最小的xx之后再算出yy，具体实现看代码。

注意会爆longlong。

代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int exgcd(int a, int b, __int128 &x, __int128 &y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}
void solve()
{
    int a, b, d;
    cin >> a >> b >> d;
    __int128 x, y;
    __int128 g = exgcd(a, b, x, y);
    if (d % g) {
        cout << -1 << '\n';
        return;
    }
    x *= (d / g);
    x %= (b / g);
    if (x < 0) {
        x += (b / g);
    }
    y = (__int128(d / g) - __int128(a / g) * x) / __int128(b / g);
    if (y < 0) {
        cout << -1 << '\n';
        return;
    }
    cout << (int)x << ' ' << (int)y << '\n';
}
signed main()
{
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

同余

  • a≡b(modn),a≡b(modm)⇒a≡b(mod[n,m])a \equiv b \pmod{n}, a \equiv b \pmod{m} \Rightarrow a \equiv b \pmod{\left [n, m \right ]}

  • a≡b(modm)⇒ka≡kb(modm)a \equiv b \pmod{m} \Rightarrow ka \equiv kb \pmod{m}

  • (k,m)=d,ka≡kb(modm)⇒a≡b(modmd)(k,m)=d,ka \equiv kb \pmod{m} \Rightarrow a \equiv b \pmod{\frac{m}{d}}

线性同余方程

给你一个方程：

ax≡b(modm)ax \equiv b \pmod{m}

我们就可以转化为：

ax−my=bax - my = b

还有一种apiad在视频里提到了的方法，我也写下来：

我们肯定有：

mx≡0(modm)mx \equiv 0 \pmod{m}

所以我们就能得到：

(m−a)x≡−b(modm)(m - a)x \equiv -b \pmod{m}

辗转相除即可。

简化剩余系和欧拉函数

懒得写前面一堆奇怪的剩余系得定义了。

所有的整数nn满足0<n≤m0 < n \leq m且(n,m)=1(n,m)=1，构成了模mm的简化剩余系。

记这样nn的个数为ϕ(m)\phi(m)，也就是大名鼎鼎的欧拉函数。

ϕ(m)=m×Πp∣mp−1p\phi(m) = m \times \Pi_{p|m} \frac{p - 1}{p}

所以我们有下面一个求欧拉函数的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
        phi /= i;
        phi *= (i - 1);
        while (n % i == 0) {
            n /= i;
        }
    }
}
if (n != 1) {
    phi /= n;
    phi *= (n - 1);
}
// phi就是n的欧拉函数值啦

我们又发现这是个积性函数，所以线性筛代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> phisieve(int n)
{
    vector<int> primes, phi(n + 1);
    vector<bool> vis(n + 1, 0);
    phi[1] = 1, phi[0] = 0;
    vis[0] = vis[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            phi[i] = i - 1;
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {  
            vis[i * primes[j]] = 1;
            if (i % primes[j]) {
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);  
            } else {
                phi[i * primes[j]] = phi[i] * primes[j];  
                break;
            }
        }
    }
    return phi;
}

两个结论：

∑d∣nϕ(d)=n\sum_{d|n}\phi(d) = n

(a,n)=1⇒aϕ(n)≡1(modn)(a,n)=1 \Rightarrow a^{\phi(n)} \equiv 1 \pmod{n}

你会发现，第二个其实是就是费马小定理的加强版。

P2398 GCD SUM

题目描述

给你一个nn，求：

∑i=1n∑j=1ngcd⁡(i,j)\sum_{i=1}^n \sum_{j=1}^n \gcd(i, j)

1≤n≤1051 \leq n \leq 10^5。

思路

原式:

=∑i=1n∑j=1n∑d∣gcd⁡(i,j)ϕ(d)=\sum_{i=1}^n \sum_{j=1}^n \sum_{d|\gcd(i,j)}\phi(d)

=∑i=1n∑j=1n∑d∣i,d∣jϕ(d)=\sum_{i=1}^n \sum_{j=1}^n \sum_{d|i, d|j}\phi(d)

=∑d=1nϕ(d)×⌊nd⌋×⌊nd⌋=\sum_{d=1}^n\phi(d)\times\left\lfloor\frac{n}{d}\right\rfloor\times\left\lfloor\frac{n}{d}\right\rfloor

代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> phisieve(int n)
{
    vector<int> primes, phi(n + 1);
    vector<bool> vis(n + 1, 0);
    phi[1] = 1, phi[0] = 0;
    vis[0] = vis[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            phi[i] = i - 1;
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {  
            vis[i * primes[j]] = 1;
            if (i % primes[j]) {
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);  
            } else {
                phi[i * primes[j]] = phi[i] * primes[j];  
                break;
            }
        }
    }
    return phi;
}
signed main()
{
    int n;
    cin >> n;
    auto phi = phisieve(n + 5);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += phi[i] * (n / i) * (n / i);
    }
    cout << ans;
    return 0;
}

逆元

威尔逊定理

组合部分