数论专题笔记

_acat_ · 2023-08-07 15:41:13 · 个人记录

1 数论中的基础知识

1.1 整除

1.1.1 定义

设 a,b 是整数，如果存在一个整数 c，使得 b=ac，则称 a 整除 b（或 b 被 a 整除），记作 a\mid b。

1.1.2 定理

1. （反射性）对于所有整数 a，满足 a \mid a。
2. （传递性）若 a \mid b，b \mid c，则 a \mid c。
3. 若 a,b_1,b_2,\cdots,b_n 都是整数，且 a \mid b_i（1 \le i \le n），则 a \mid b_1c_1+b_2c_2+\cdots+b_nc_n（\forall c_1,c_2,\cdots,c_n \in \mathbb{Z}）。
4. 若 a,b_1,b_2,\cdots,b_n 都是整数，且 a \mid b_i（1 \le i \le n），则 a \mid b_1c_1 \times b_2c_2 \times \cdots \times b_nc_n（\forall c_1,c_2,\cdots,c_n \in \mathbb{Z}）。
5. 若 a \mid b，a \mid b \pm c，则 a \mid c。
6. 若整数 a,b,c,d,e 满足 a \mid b-c，a \mid d-e，则 a \mid bd - ce。
7. 若 a\mid b，则 \forall c \in \mathbb{Z}，ac\mid bc；若 ac \mid bc 且 c \ne 0，则 a\mid b。

1.1.3 证明

定理 1、2、7 可直接由定义推导，定理 3-6 通过将 b_i 表示为 a \times w_i（w_i 为整数），代入等式后化简可证。

1.2 同余

1.2.1 定义

设 a,b,n 是整数，若 n \mid a-b，则称 a 和 b 模 n 同余，记作 a \equiv b \pmod {n}。

1.2.2 定理

1. （反射性）a \equiv a \pmod n。
2. （对称性）若 a \equiv b \pmod n，则 b \equiv a \pmod n。
3. （传递性）若 a \equiv b \pmod n 且 b \equiv c \pmod n，则 a \equiv c \pmod n。
4. 若 a \equiv c \pmod n 且 b \equiv d \pmod n，则 a+b \equiv c+d \pmod n，ab \equiv cd \pmod n。
5. 若 a \equiv b \pmod n，则 ac \equiv bc \pmod {nc}；若 ac \equiv bc \pmod {nc} 且 c \ne 0，则 a \equiv b \pmod n。

1.2.3 证明

定理 1、2 由定义直接成立；定理 3-5 利用整除性质推导，例如定理 3 可通过 n \mid (a-b)+(b-c) = a-c 证明。

1.3 数论函数

定义域为正整数、值域为复数集子集的函数称为数论函数。

1.3.1 积性函数

• 积性函数：\forall x,y \in \mathbb{N}_+ 且 \gcd(x,y)=1，满足 f(xy)=f(x)f(y)。
• 完全积性函数：\forall x,y \in \mathbb{N}_+，满足 f(xy)=f(x)f(y)（完全积性必为积性）。
• 常见积性函数：
  • 1 函数（完全积性）：\mathbb{1}(n)=1
  • 幂函数（完全积性）：id_k(n)=n^k
  • 狄利克雷卷积单位元（完全积性）：\varepsilon(n)= \begin{cases} 1, & n=1 \\ 0, & n \ne 1\end{cases}
  • 欧拉函数：\varphi(n)（1\sim n 中与 n 互质的数的个数）
  • 除数函数：d(n)（n 的正因子个数）

1.3.2 加性函数

• 加性函数：\forall x,y \in \mathbb{N}_+ 且 \gcd(x,y)=1，满足 f(xy)=f(x)+f(y)。
• 完全加性函数：\forall x,y \in \mathbb{N}_+，满足 f(xy)=f(x)+f(y)（完全加性必为加性）。
• 常见加性函数：

1.4 模运算

带余除法：\forall a,b>0，存在唯一整数 q,r 满足 a=bq+r（0 \le r <b），r 记为 a \bmod b。

运算法则：

1. (a+b) \bmod M = (a \bmod M + b \bmod M) \bmod M
2. (a-b) \bmod M = (a \bmod M - b \bmod M) \bmod M
3. (a \times b) \bmod M = (a \bmod M \times b \bmod M) \bmod M

注意：除法无直接模运算法则，需通过逆元转换。

2 素数

2.1 唯一分解定理

每个大于 1 的整数都能唯一表示为质因数之积：n=\prod p_i^{a_i}（p_i 为素数，p_1<p_2<\cdots，a_i \ge 1）。

推论：n 中最多含有一个大于 \sqrt{n} 的因子。

分解代码：

void decompose(int x){
    for(int i=2;i*i<=x;++i)
        while(x%i==0) ++a[i],x/=i;
    if(x) ++a[x];
}
int main(){
    int n;scanf("%d",&n);
    decompose(n);
    for(int i=1;i<=n;++i) 
        if(a[i]) printf("%d %d\n",a[i],i);
}

2.2 费马小定理若

5 模意义下的乘法逆元

5.1 定义

若 ax \equiv 1 \pmod p，则 x 为 a 在模 p 下的逆元，记为 a^{-1} \pmod p。

5.2 逆元求法

5.2.1 扩展欧几里得求逆元

将 ax \equiv 1 \pmod p 转化为 ax + py = 1，调用 exgcd 求解 x（要求 \gcd(a,p)=1）。

5.2.2 费马小定理求逆元

• 常见卷积：1*\varphi=id，1*\mu=\varepsilon

8.1.2 莫比乌斯函数

8.2 莫比乌斯反演

• 形式 1：若 g(x)=\sum_{k|x} f(k)，则 f(x)=\sum_{k|x} \mu(x/k)g(k)。
• 形式 2：若 g(x)=\sum_{x|k} f(k)，则 f(x)=\sum_{x|k} \mu(k/x)g(k)。

8.3 整除分块

用于快速计算 \sum_{i=1}^n \lfloor n/i \rfloor 类求和，时间复杂度 O(\sqrt{n})：

for (int l = 1, r; l <= n; l = r + 1)
    r = n / (n / l),
    ans += (r - l + 1) * (n / r);

8.4 杜教筛

快速求积性函数前缀和，核心公式：

（其中 f \times g=h，G 为 g 的前缀和）模板代码（求 \mu(x) 前缀和）：

const int N = 5e6 + 5;
int miu[N], p[N];
bool is_p[N];
map <int, int> mp;

void sieve(int N) {
    miu[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!is_p[i]) p[++c] = i, miu[i] = -1;
        for (int j = 1; j <= c && i * p[j] <= N; j++) {
            is_p[i * p[j]] = 1;
            if (i % p[j] == 0) { miu[i * p[j]] = 0; break; }
            miu[i * p[j]] = -miu[i];
        }
    }
    for (int i = 2; i <= N; i++) miu[i] += miu[i - 1];
}

int cal_miu(int x) {
    if (x <= 5e6) return miu[x];
    if (mp.count(x)) return mp[x];
    int res = 1;
    for (int l = 2, r; l <= x; l = r + 1)
        r = x / (x / l),
        res -= (r - l + 1) * cal_miu(x / r);
    return mp[x] = res;
}

8.5 Powerful Number 筛（PN 筛）

适用于杜教筛无法解决的函数，核心是利用“幂数”（所有质因子次数 \ge 2）的稀疏性（n 以内幂数个数为 O(\sqrt{n})）。

模板代码（Min_25 筛替代）：

const int mod = 1e9 + 7;
const int inv2 = 500000004;
const int inv6 = 166666668;
const int N = 5e6 + 5;
int p[1000000], phi[N], c;
bool is_p[N];

void sieve(int N) {
    phi[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!is_p[i]) p[++c] = i, phi[i] = i - 1;
        for (int j = 1; j <= c && i * p[j] <= N; j++) {
            is_p[i * p[j]] = 1;
            if (i % p[j] == 0) { phi[i * p[j]] = phi[i] * p[j]; break; }
            phi[i * p[j]] = phi[i] * (p[j] - 1);
        }
    }
    for (int i = 2; i <= N; i++) (phi[i] *= i) %= mod;
    for (int i = 2; i <= N; i++) (phi[i] += phi[i - 1]) %= mod;
}

int mp[N], n, ans;
int cal_G(int x) {
    if (x <= 5e6) return phi[x];
    if (mp[n / x]) return mp[n / x];
    int X = x % mod;
    int res = X * (X + 1) % mod * (2 * X + 1) % mod * inv6 % mod;
    for (int l = 2, r; l <= x; l = r + 1)
        r = x / (x / l),
        res -= (l + r) % mod * (r - l + 1) % mod * inv2 % mod * cal_G(x / r);
    return mp[n / x] = res;
}

void dfs(int nw, int num, int H) {
    if (nw > c || num * p[nw] > n) {
        (ans += H * cal_G(n / num)) %= mod;
        return;
    }
    dfs(nw + 1, num, H);
    for (int mu = p[nw] * p[nw], s = 1; num * mu <= n; mu *= p[nw], s++)
        dfs(nw + 1, num * mu, s * (p[nw] - 1) % mod * mu % mod * H % mod);
}

signed main() {
    scanf("%lld", &n), sieve(5e6), dfs(1, 1, 1);
    printf("%lld", ans);
}