2024.12.23 数论 2 讲课笔记

szt100309 · 2024-12-23 19:01:10 · 个人记录

以下 a//b 表示 \lfloor\frac ab\rfloor，Adn(n)=\frac{n(n+1)}2，Fc(L,R)=Adn(R)-Adn(L-1)

类欧几里得

模板题：P5170 【模板】类欧几里得算法

给定 n,a,b,c ，分别求 \sum_{i=0}^{n}(ai+b)//c, \sum_{i=0}^{n}{((ai+b)//c)}^2, \sum_{i=0}^{n}i\cdot(ai+b)//c 取模，多测 t\le10^5，0\le n,a,b,c\le10^9,c\ne 0

令

三者同步递归计算

当 a=0 时，显然有

当 a\ge c 或 b\ge c 时，有

转化为求解 g(n,a\bmod c,b\bmod c,c),h(n,a\bmod c,b\bmod c,c),f(n,a\bmod c,b\bmod c,c)

当 0\le a< c 且 0\le b<c 时，令 m=(an+b)//c，有：

转化为求解 f(m-1,c,c-b-1,a),g(m-1,c,c-b-1,a),h(m-1,c,c-b-1,a)

递归求解，可证这样时间复杂度为 O(\log\max(a,c))

代码

例 1：CF1098E Fedya the Potter

给定 a_{1\sim n}，令 b 为可重集 \left\{\gcd_{l\le k\le r} a_k\mid1\le l\le r\le n\right\} 排序后的结果，c 为可重集 \left\{\sum_{l\le k\le r}b_k\mid1\le l\le r\le n\right\} 排序后的结果，求 c 的中位数，n\le5\times10^4,1\le a_i\le10^5

对于一个 r，|\left\{\gcd_{l\le k\le r} a_k\mid1\le l\le r\right\}|=O(\log n)

因此先对 a 建立 gcd 的 ST 表，然后枚举 r，通过 O(\log n) 次二分将 [1,r] 划分为 O(\log n) 块，满足对于任意一块 S=[L,R]，\gcd_{l\le k\le r} a_k\;(L\le l\le R) 值相同，从而求出 cnt_i，表示 \gcd_{l\le k\le r} a_k=i 的 (l,r) 数量（即代码中的 b 数组），这部分时间复杂度为小常数的 O(n\log^2 n\log V)

这样 b 即为 cnt_1 个 1 拼接上 cnt_2 个 2 拼接上 ······ 拼接上 cnt_{V} 个 V，其中 V 为值域大小

二分中位数 M，问题转化为求出 b 中有多少区间和不超过 M 的区间

称 cnt_k 个 k 为第 k 段

在第 k 段中，一共有 Fc(cnt_i-\min(cnt_i,M//i)+1,cnt_i) 个区间和 \le M 的区间，这部分容易 O(V) 计算

对于跨段的区间，设其左端点位于第 l 段，右端点位于第 r 段

预处理 ct_i=\sum_{j=1}^i cnt_j，sm_i=\sum_{j=1}^i cnt_j\cdot j

若 sm_r-sm_{l-1}\le M，则第 l 段内任意位置和第 r 段内任意位置都合法

若 sm_r-sm_{l-1}>M 且 sm_{r-1}-sm_l+l-r\le M，则第 l 段内和第 r 段内部分位置合法

其他情况全不合法

因此枚举右端点，双指针或二分确定上述两种情况的范围，前者容易通过 ct 和 b 数组单次 O(1)算出，后者可转化为给定 n,m,a,b,c，求 \sum_{i=1}^n\sum_{j=1}^m [ai+bj\le c]

令 F(a,b,c)=\sum_{i=1}^\infty\sum_{j=1}^\infty [ai+bj\le c]，则 \sum_{i=1}^n\sum_{j=1}^m [ai+bj\le c]=F(a,b,c)-F(a,b,c-an)-F(a,b,c-bn)+F(a,b,c-an-bn)

转化为类欧几里得的形式，可 O(\log\max(c\bmod a,b))=O(\log\max(a,b))

总时间复杂度 O(n\log^2n\log V+(\log n+\log V)V\log V)=O(n\log n^2\log V+V\log^2V)，瓶颈在于求 cnt 的过程

代码

例 2：P5172 Sum

给定 T 组 n,r，求 \sum_{d=1}^n (-1)^{\lfloor d\sqrt r\rfloor}，T\le10^4,n\le10^9,r\le10^4

若 r 为完全平方数，设 r=x^2，则 \sum_{d=1}^n (-1)^{\lfloor d\sqrt r\rfloor}=\sum_{d=1}^n (-1)^{dx}=\sum_{d=1}^n ((-1)^x)^d，若 x 为偶数则答案为 n，否则若 n 为奇数答案为 -1，为偶数答案为 0

否则由于 (-1)^x=1-2(x\bmod 2)=1-2(x-2(x//2))=1-2x+4(x//2)，原式等于 n-2\sum_{d=1}^n\lfloor d\sqrt r\rfloor+4\sum_{d=1}^n\lfloor \frac {d\sqrt r}2\rfloor

转化为求解形如 \sum_{i=1}^n\lfloor\frac{a\sqrt r+b}c\cdot i\rfloor 的式子

令 f(n,a,b,c,r)=\sum_{i=1}^n\lfloor\frac{a\sqrt r+b}c\cdot i\rfloor

否则先对 \frac{a\sqrt r+b}c 约分（a,b,c 都除以 \gcd(a,b,c)，若不约分则中间过程可能超过 long long，若约分则可保持在 int 范围内）

令 t=\frac{a\sqrt r+b}c

若 t\ge 1，则取出其整数部分，可得 f(n,a,b,c,r)=f(n,a,b-c\lfloor t\rfloor,c,r)+\lfloor t\rfloor\cdot\frac{n(n+1)}2

若 0\le t<1，则

递归处理即可

可证时间复杂度为 O(T\log n)

代码

万能欧几里得

在平面上有线段 y=\frac{px+r}q\{0< y\le n\}，其中 p,q,r 为整数。有变换 U、R 和初始值 S，从原点出发，先向上到达 (0,\frac rq)，然后从左往右沿线段行走，若横坐标为整数则 S\leftarrow S\times U，若纵坐标为整数则 S\leftarrow S\times R，若都为整数则 S\leftarrow S\times U\times R，求最终的 S，0\le p,q,r\le10^9,q\ne0，变换有结合律

设 f(n,p,q,r,U,R) 为上述所有变换之积

• 若 r\ge q，则最前面向上走的一段含有 r//q 个 U，得到

  f(n,p,q,r,U,R)=U^{r//q}\times f(p\bmod q,q,r,n,U,R)

• 若 p\ge q，则 y=\frac pq\cdot x+\frac rq，若 x 要加一则 y 增加 \frac pq，其中至少经过 p//q 个 U，即每个 R 之前至少有 p//q 个 U，将其和这个 R 合并，得到

  f(n,p,q,r,U,R)=f(p\bmod q,q,r,n,U,U^{p//q}R)

• 否则，考虑翻转 x 轴和 y 轴

  直线 y=\frac{px+r}q 翻转得到 x=\frac{qy-r}p

  由于原先遇到整点要先算 U，因此翻转之后要先算 R，将 x 减少 \epsilon，得到 x=\frac{qy-r-1}p

  翻转之后的定义域为原先的值域 (\frac rq,\frac {pn+r}q]（以下令 m={(pn+r)}//q）

  若 m=0，则无需翻转，此时不存在 U，得到 f(n,p,q,r,U,R)=R^{n}

  否则

  f(n,p,q,r,U,R)=R^{{(q-r-1)}//{p}}U\cdot f(q,p,(q-r-1)\bmod p,n,R,U)\cdot R^{n-(qm-r-1)//p}

若使用快速幂实现，则可证时间复杂度为 O(T\log\max(p,q))，其中 T 为单次变换时间

模板：

namespace euclid {
    using ll = long long;
    inline constexpr ll cal(ll a, ll b, ll c, ll d){return (__int128_t(a) * b + c) / d;}//fma(a, b, c) / d
    template <typename _Tp> inline _Tp fpw(_Tp a, ll b, _Tp e){for (; b; b >>= 1, a = a * a)if (b & 1)e = e * a;return e;}
    template <typename _Tp> _Tp euclid(ll p, ll q, ll r, ll n, const _Tp &U, const _Tp &R, const _Tp &e/*unit*/){
        if (!n)return e;
        if (r >= q)return fpw(U, r / q, e) * euclid(p, q, r % q, n, U, R, e);
        if (p >= q)return euclid(p % q, q, r, n, U, fpw(U, p / q, e) * R, e);
        ll m = cal(p, n, r, q);if (!m)return fpw(R, n, e);
        return fpw(R, (q - r - 1) / p, e) * U * euclid(q, p, (q - r - 1) % p, m - 1, R, U, e) * fpw(R, n - cal(q, m, -r - 1, p), e);
    }
}

考虑用万欧解决类欧模板

所有操作都可用矩阵描述

需要取出有用位置，否则常数过大

例：LOJ #6440. 万能欧几里得

给定矩阵 A,B 和 n,p,q,r，求 \sum_{i=1}^n A^i B^{(ip+r)//q}，n\le20,p,q,r\le10^{18}

在万欧过程中维护 \sum x，\sum y，\sum xy 即可

由于矩乘没有交换律，需要注意合并顺序

代码

参考

积性函数 和 狄利克雷卷积

常用积性函数

单位函数 \varepsilon(n)=[n=1]

恒等函数 \operatorname{id}_k(n)=n^k，若 k=1 则省略

常函数 I(n)=1，有时也写为 \operatorname{1}(n)

除数函数 \sigma_k(n)=\sum_{d\mid n}d^k，k=1 时省略，k=0 时即为因子数 d(n)

欧拉函数 \varphi(n)

莫比乌斯函数 \mu(n)

狄利克雷卷积

• \sigma_k=\operatorname{id}_k\ast I
• \varphi=\mu\ast \operatorname{id}
• \operatorname{id}=\varphi\ast I

杜教筛

若可以构造 g 和 h，满足 f\ast g=h 且可以在不超过 O(n^{3/4}) 的复杂度内求出所有 n//i 处的 g 和 h 的前缀和，则可以 O(n^{3/4}) 求解（若 f 为积性函数，则可以线性筛预处理 1\sim n^{2/3} 的 f 的前缀和，做到 O(n^{2/3})，当然此时 g 和 h 的前缀和需要 O(n^{2/3}) 内求出），同时求出所有 n//i 处的前缀和

令 F,G,H 为 f,g,h 的前缀和

有 H(n)=\sum_{i=1}^n h(i)=\sum_{ij\le n}f(j)g(i)=\sum_{i=1}^n g(i) F(n//i)=g(1)F(n)+\sum_{i=2}^n g(i)F(n//i)

则 F(n)=\frac{H(n)-\sum_{i=2}^n g(i)F(n//i)}{g(1)}

数论分块即可

需要记忆化

模板题：P4213 【模板】杜教筛

求 \varphi 和 \mu 的前缀和，n\le INT\_MAX

由于 \varepsilon=\mu\ast I ，\operatorname{id}=\varphi\ast I，直接套模板即可

代码

Powerful Number 筛

要求 f 为积性函数，其质数处取值可快速计算，且存在积性函数 g，满足两者质数处取值相同，且 g 可快速求所有 n//i 处的前缀和

定义 Powerful\;\; Number（PN）为 \nexists (p\mid x,p\in\{Prime\}),p^2\nmid x 的 x

可证 PN 都能表示为 a^2b^3，n 以内 PN 只有 O(\sqrt n) 个

构造 h 为满足 g\ast h=f 的函数，显然其为积性函数

若 p 为素数，则 f(p)=g(1)h(p)+g(p)h(1)=h(p)+g(p)，由于 f(p)=g(p)，有 h(p)=0，即只有 PN 处 h 才可能非 0

类似杜教筛，可得 F(n)=\sum_{i=1}^n h(i)G(n//i)，由于 i\ne \{PN\} 时 h(i)=0，因此 F(n)=\sum_{i\in\{PN\},i\le n}h(i)G(n//i)

由于 G 可快速求出，要求 F(n)，问题转化为求 h(i)\;(i\in\{PN\})

要求 h(p^c) 有两种方法，一种是根据题目推式子，还有一种是可证 h(p^c)=f(p^c)-\sum_{i=1}^c g(p^i)h(p^{c-i})，枚举计算即可

总流程为：

1. 筛出 \sqrt n 内质数
2. 枚举 p 和 c，求出所有 h(p^c)
3. 根据 p 搜索出所有 PN，求出 PN 处的 h 的值
4. 求出 n//i 处的 G 的值
5. 得到 F(n)

除第 2 步外时间复杂度为 O(\sqrt n)，第二步若采用第二种方法则时间复杂度为宽松的 O(\sqrt n\log n)，有时可继续优化

若使用杜教筛计算 G，则时间复杂度为 O(n^{2/3})

空间复杂度为 O(\sqrt n)

例：LOJ #6053. 简单的函数

有积性函数 f 满足 f(p^c)=p\oplus c，给定 n ，求 f 前缀和，n\le10^{10}

构造 g(n)=\begin{cases}3\varphi(n)&n\bmod2=0\\\varphi(n)&n\bmod2=1\end{cases}

根据 PN 筛的方式，以下只考虑计算 G

可证 G(n)=\sum_{i=1}^n\varphi(i)+2\sum_{i=1}^{n//2}\varphi(2i)

令 S_1(n)=\sum_{i=1}^n\varphi(i),S_2(n)=\sum_{i=1}^{n//2}\varphi(2i)，可证 S_2(n)=S_1(n)+S_2(n//2)，显然 S_1 可以杜教筛求解，S_2 在求出 S_1 必须值的基础上可单次 O(\log n) 求解

总时间复杂度 O(n^{2/3})

也可用 Min\_25 筛做，只要注意 f(2) 的处理，代码

Min_25 筛

具体介绍见 文章 Min_25 筛

例 1：LOJ #6235. 区间素数个数

取 Min\_25 筛前半部分即可

代码

例 2：P5325 【模板】Min_25 筛

模板题，代码

vjudge 练习

Number Theory 2，pw:edgeedgeweloveyou

luogu 题单

24.12.23 math2

参考

math2.pdf by Tx_Lcy

oi-wiki 数论