数论#

中国剩余定理(CRT)#

m_2 \cdot m_3 \cdot x \equiv 1 \pmod{m_1}

a_1 \cdot (m_2 \cdot m_3 \cdot x) \equiv a_1 \pmod{m_1}

扩展CRT#

1
using ll = long long;
2

3
// 扩展gcd
4
ll exgcd(ll a, ll b, ll &x, ll &y) {
5
    if (!b) {
6
        x = 1; y = 0;
7
        return a;
8
    }
9
    ll x1, y1;
10
    ll g = exgcd(b, a % b, x1, y1);
11
    x = y1;
12
    y = x1 - a / b * y1;
13
    return g;
14
}
15

16
// 扩展CRT
17
// a[i] ≡ x (mod m[i])
18
// 返回 (x, lcm) 或 (-1, -1) 表示无解
19
pair<ll, ll> excrt(vector<ll>& a, vector<ll>& m) {
20
    ll A = a[0], M = m[0];
21

22
    for (int i = 1; i < a.size(); ++i) {
23
        ll a2 = a[i], m2 = m[i];
24

25
        ll x, y;
26
        ll g = exgcd(M, m2, x, y);
27

28
        ll c = a2 - A;
29
        if (c % g != 0) return {-1, -1}; // 无解
30

31
        // 防溢出写法
32
        ll mod = m2 / g;
33
        x = (__int128)x * (c / g) % mod;
34

35
        A = A + x * M;
36
        M = M / g * m2;
37

38
        A = (A % M + M) % M;
39
    }
40

41
    return {A, M};
42
}

快速乘#

unsigned long long 溢出相当于对 $2^{64}$ 取余

1
ll qmul(ll a, ll b, ll p) {
2
  ll q = (ld)a / p * b;
3
  ll res = (ull)a * b - (ull)q * p;
4
    return (res + p) % p;
5
}

快速幂#

1
ll qmi(ll a, ll b, ll p) {
2
    ll res = 1 % p;
3
     while (b) {
4
        if (b & 1) res = res * a % p;
5
        a = a * a % p;
6
        b >>= 1;
7
    }
8
    return res;
9
}

扩展欧几里得定理(EXGCD)#

求as + bt = gcd(a, b)的s和t

25s + 11t = gcd(11, 3)

11s1 + 3t1 = gcd(3, 2)

3s2 + 2t2 = gcd(2, 1)

2s3 + t3 = gcd(1, 0)

s4 = 1, t4 = 0

as + bt = bs' +rt'

q = \lfloor\frac{a}{b}\rfloor

r = a - bq

as + bt = bs' + (a - \lfloor\frac{a}{b}\rfloor \cdot b)\cdot t'

as + bt = at' + b \cdot(s' - qt')

s = t’, t = s’ - qt’

1
pair<int, int> extgcd(int a, int b) {
2
  if (!b) return make_pair(1, 0);
3
  auto [s, t] = extgcd(b, a % b);
4
    return make_pair(t, s - a / b * t);//t * (1,s/t-a/b)
5
}

欧拉定理#

gcd(a, m) = 1

a^{\varphi(m)} \equiv 1 \pmod{m}

费马小定理#

本身为欧拉定理的特例

p是素数，gcd(a, m) = 1, 有

a^p \equiv a \pmod{p}

a^{p-1} \equiv 1 \pmod{p}

既约剩余系 * 任意数a的数是既约剩余系的重排列

乘法在同余等价关系上有幺元，当乘数和模数互素时有逆元

gcd(a, n) = 1

贝祖定理 as + nt = 1，则有

as \equiv 1 \pmod{n}

则a有逆元s，同时可以进行同余除法

命题#

设模 ( n ) 的既约剩余系为：

[ R = {r_1, r_2, \dots, r_{\varphi(n)}} ]

其中：

[ \gcd(r_i, n) = 1 ]

若整数 ( a ) 满足：

[ \gcd(a, n) = 1 ]

则集合：

[ aR = {ar_1, ar_2, \dots, ar_{\varphi(n)}} \pmod n ]

仍然是模 ( n ) 的一个既约剩余系（只是一个重排列）。

证明思路#

分三步：

第一步：仍然互质#

因为：

[ \gcd(a,n)=1,\quad \gcd(r_i,n)=1 ]

则：

[ \gcd(ar_i, n)=1 ]

理由：

\text{若某质因子 } ( p \mid n )， \text{由于 } ( a ) \text{ 与 } ( n ) \text{ 互质，} ( p \nmid a ) \text{由于 } ( r_i ) \text{ 与 } ( n ) \text{ 互质，} ( p \nmid r_i )

因此：

[ p \nmid ar_i ]

故：

[ \gcd(ar_i,n)=1 ]

所以每个元素仍在单位群里。

第二步：不会产生重复#

假设：

[ ar_i \equiv ar_j \pmod n ]

则：

[ a(r_i - r_j) \equiv 0 \pmod n ]

因为：

[ \gcd(a,n)=1 ]

所以 ( a ) 在模 ( n ) 下可逆。乘以 ( a^{-1} ) 得：

[ r_i \equiv r_j \pmod n ]

但既约剩余系中本来互不相同，因此：

[ i=j ]

所以不会出现重复。

第三步：个数相同#

原集合有：

[ \varphi(n) ]

个元素。

现在：

每个元素仍互质
无重复
个数不变

因此必然是既约剩余系的一个排列。

质数#

筛法#

线性筛法

1
int primes[N], idx;
2
bool vis[N];
3
void getp(int n) {
4
    memset(primes, 0, sizeof primes);
5
    primes[1] = 0;
6
    for (int i = 2; i <= n; ++i) {
7
        if (!vis[i]) primes[++idx] = i;
8
    for (int j = 1; i * primes[j] <= n; ++j) {
9
      vis[i * primes[j]] = 1;
10
            if (i % primes[j] == 0) break;
11
        }
12
    }
13
}

埃筛

1
int primes[N], idx;
2
bool vis[N];
3
void getp(int n) {
4
    for (int i = 2; i <= n; ++i) {
5
        if (vis[i]) continue;
6
        primes[idx++] = i;
7
        for (int j = i; j <= n / j; ++j) {
8
            vis[j * i] = 1;
9
        }
10
    }
11
}

约数#

质因数分解#

纯暴力

1
unordered_map<int, int> pcnt;
2

3
void getfactor(int n) {
4
    for (int i = 2; i <= n / i; ++i) {
5
        while (n % i == 0) {
6
            ++pcnt[i];
7
            n /= i;
8
        }
9
    }
10
}

阶乘的质因数分解

\text{p 指数的数量}=\sum_{k = 0}^{\infty}{\lfloor \frac{N}{p^k} \rfloor}

约数计算#

\text{质因数分解 } p_0^{c_0} p_1^{c_1} \cdots p_k^{c_k}

\text{约数之和}=\sum_{i = 0}^{k}\sum_{j=0}^{c_i}{p_i^j}

\text{约数的数量}=\prod_{i=0}^{k}{(c_i + 1)}

欧拉函数#

\varphi(p) = \text{[1, } p - 1 \text{] 内与 } p \text{ 互质的数的数量}

性质#

gcd(m,n) = 1 \Rightarrow \varphi(mn) = \varphi(m) \cdot \varphi(n)

音乐

音乐

数论#

中国剩余定理(CRT)#

扩展CRT#

快速乘#

快速幂#

扩展欧几里得定理(EXGCD)#

欧拉定理#

费马小定理#

命题#

证明思路#

第一步：仍然互质#

第二步：不会产生重复#

第三步：个数相同#

质数#

筛法#

约数#

质因数分解#

约数计算#

欧拉函数#

性质#

文章分享

评论区

音乐

目录

音乐

音乐

7-数论

数论#

中国剩余定理(CRT)#

扩展CRT#

快速乘#

快速幂#

扩展欧几里得定理(EXGCD)#

欧拉定理#

费马小定理#

命题#

证明思路#

第一步：仍然互质#

第二步：不会产生重复#

第三步：个数相同#

质数#

筛法#

约数#

质因数分解#

约数计算#

欧拉函数#

性质#

文章分享

评论区

音乐

目录