2.18数论

A

题意

有一个$n\times m$的表格，第$i$行$j$列的值为$\gcd(i, j)$。给出一个数列$a$，判断它是否在表格的某一行出现过。

$$n,m\leq 10^{12},|a|\leq 10^4$$

题解

求出$a_i$的$\text{lcm}$。显然行必须是这个$\text{lcm}$的倍数。同时行取这个$\text{lcm}$的时候最优，因为如果取$\text{lcm}$的倍数的话会产生额外的质因子干扰$\gcd$，同时我们也应满足行的编号尽量小。

接下来考虑列。假设这个数列$a$对应第$i$行的第$j+1,j+2,\cdots, j+|a|$列，那么对于每个$k$我们有$a_k|j+k$，即$j\equiv a_k-k\bmod a_k$。用中国剩余定理合并之后可以得到$j\equiv x\bmod \text{lcm}(\{a\})$。求出最小的非负整数解$x$，由于$a_k|\text{lcm}(\{a\})$，根据$\gcd$的性质我们可以发现当$j$取这个$x$的时候最优。接下来扫一遍$a$，根据定义判断$a$是否在第$i$行$j$列合法即可。

B

题意

$$\sum_{i=a}^b\text{lcm}(i, b)\bmod 10^9+7$$

$T\leq 5000$组数据，$a,b\leq 10^9$。

题解

$$\sum_{i=a}^b\text{lcm}(i,b)=b\sum_{i=a}^b\frac{i}{\gcd(i,b)}$$

假设我们找到了一组系数$f(n)$使得$\sum_{d|n}f(d)=\frac{1}{n}$。那么

$$\begin{aligned} \sum_{i=a}^b\frac{i}{\gcd(i,b)}&=\sum_{i=a}^bi\sum_{d|i,d|b}f(d)\\ &=\sum_{d|b}f(d)\sum_{i=a}^b[d|i] \end{aligned}$$

第二个$\sum$里面的东西相当于求出一段区间内有多少个数是$d$的倍数，这非常好求。如果我们能算出$f$，那么只需要枚举$b$的所有因数就可以计算答案。

考虑如何算$f$。首先，由于$\frac{1}{x}$是个积性函数，因此$f$也必然是积性函数。

$$\begin{aligned} f(1)&=\frac{1}{1}=1\\ f(1)+f(p)&=\frac{1}{p}\Rightarrow f(p)=\frac{1}{p}-1\\ f(1)+f(p)+f(p^2)+\cdots+f(p^k)&=\frac{1}{p^k}\Rightarrow f(p^k)=\frac{1}{p^k}-\frac{1}{p^{k-1}} \end{aligned}$$

因此，我们可以得到$f(n)=\frac{1}{n}\prod (1-p_i)$。这里$p_i$是$n$的所有质因子。

C

题意

$$\sum_{i=a}^b\frac{1}{i}\sum_{j=1}^i\text{lcm}(j,i)\bmod 10^9+7\\\ a,b\leq 10^{10}$$

题解

$$\begin{aligned} \sum_{i=1}^n\frac{1}{i}\sum_{j=1}^i\text{lcm}(j,i)&=\sum_{i=1}^n\sum_{j=1}^i\frac{j}{\gcd(j, i)}\\ &=\sum_{i=1}^n\sum_{j=1}^ij\sum_{d=1}^n\frac{1}{d}[\gcd(j,i)=d]\\ &=\sum_{d=1}^n\sum_{i=1}^{\frac nd}\sum_{j=1}^ij[\gcd(j,i)=1] \end{aligned}$$

此时最后一个$\sum$相当于$1\sim i$中与$i$互质的数之和，它等于$\frac{i\varphi(i)}{2}$。注意当$i=1$时要特判。

D

题意

$$\sum_{i=1}^n\sum_{d|i}\gcd(d,\frac id),n\leq 10^{12}$$

题解

$$\begin{aligned} \sum_{i=1}^n\sum_{d|i}\gcd(d,\frac id)&=\sum_{d=1}^n\sum_{i=1}^{\frac nd}\gcd(d,i)\\ &=\sum_{d=1}^n\sum_{i=1}^{\frac nd}\sum_{j|d,i}\varphi(j)\\ &=\sum_{j=1}^n\varphi(j)\sum_{d=1}^{\frac nj}\lfloor\frac{n}{dj^2}\rfloor \end{aligned}$$

注意到$j$只用枚举到$\sqrt n$，最终复杂度为

$$\sum_{i=1}^\sqrt n\sqrt \frac{n}{i^2}=\sum_{i=1}^\sqrt n\frac{\sqrt n}{i}=\sqrt n\log(n)$$

E

题意

定义$d(x)$是满足$y|x$且$y>1$的最小正整数$y$。

定义

$$f(x)=\begin{cases}1&x=1\\\ d(x)f\left(\frac{x}{d(x)^2}\right)&x>1,d(x)^2\mid x\\\ f\left(\frac{x}{d(x)^2}\right)&\text{others}\end{cases}$$

求$\sum_{i=1}^nf(i)$

题解

有两种做法。

$d(x)$实际上就是$x$的最小质因子，观察$f$的式子可以发现，

$$f(x)=\prod p_i^{\lfloor\frac {k_i}2\rfloor}$$

它等价于

$$\max_{u^2\mid x}u$$

如果$u$满足$u\mid x$，那么$u$以及它的所有因数也满足这个条件，并且只有这些数满足条件

因此我们可以将这个东西变换一下

$$\max_{u^2\mid x}u=\sum_{u^2|x}\varphi(u)$$

因此我们实际上要求的就是

$$\begin{aligned} \sum_{i=1}^nf(i)&=\sum_{i=1}^n\sum_{u^2\mid i}\varphi(u)\\ &=\sum_{u=1}^{\sqrt n}\varphi(u)\lfloor\frac n{u^2}\rfloor \end{aligned}$$

第二种做法是直接考虑powerful number筛。

定义powerful number为所有质因数的质数均$\geq 2$的数，可以证明$\leq n$的powerful number只有$O(\sqrt n)$个。

回到这道题，不难看出$f(x)$是积性函数。

考虑求出$h(x)$满足$f(n)=\sum_{d|n}h(d)$。我们有

$$\begin{aligned} h(1)&=f(1)=1\\ h(1)+h(p)&=f(p)\Rightarrow h(p)=0\\ \end{aligned}$$

同时，$h(p^k)$是很好算的东西，这里就不推了。

注意到当$p$是质数时，$h(p)=0$，也就是说，$h$在所有非powerful number处取值都为$0$。

暴力搜出$n$以内的所有powerful number，然后用这个$h(n)$求值即可。

F

题意

记$\text{sgcd}(i,j)$为$i,j$的公约数中第二大的，特别地若$\gcd(i,j)=1$，定义$\text{sgcd}(i,j)=0$。

求

$$\sum_{i=1}^n\sum_{j=1}^n\text{sgcd}(i,j)^k,n\leq 10^9,k\leq 50$$

题解

记$\text{minp}(x)$为$x$的最小质因子，特别地若$x=1$则$\text{minp}(x)=\infty$。

那么问题等价于

$$\begin{aligned} \cdots&=\sum_{i=1}^n\sum_{j=1}^n\sum_{d=1}^n\left(\frac{d}{\text{minp}(d)}\right)^k[\gcd(i,j)=d]\\ &=\sum_{d=1}^n(\cdots)^k\sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac nd}[\gcd(i,j)=1]\\ &=\sum_{d=1}^n(\cdots)^k(2\sum_{i=1}^{\frac nd}\varphi(i)-1) \end{aligned}$$

第二个$\sum$可以使用一次杜教筛解决，问题转化为求$\left(\frac d{\text{minp}(d)}\right)^k$的前缀和。这个可以用类似min25筛的方式解决。

记$F(i,j)$表示考虑$[1,j]$中的数，最小质因子大于第$j$个质数的所有数的$k$次方之和。

记$G(i,j)$表示考虑$[1,j]$中的数，最小质因子大于第$j$个质数的数的个数。

记$H(i,j)$表示考虑$[1,j]$中的数，最小质因子不超过第$j$个质数的所有数的答案之和。

那么有

$$\begin{aligned} F(i,j)&=F(i-1,j)-p_i^kF(i-1,\frac{j}{p_i})\\ G(i,j)&=G(i-1,j)-G(i-1,\frac{j}{p_i})\\ H(i,j)&=H(i-1,j)+F(i-1,\frac{j}{p_i}) \end{aligned}$$

当$p_j>\sqrt n$时，最小质因子为$p_j$的数只有$p_j$，且它的答案为$1$。

用类似min25筛的方式$dp$一下即可。

G

题意

给定$x,a,b$，求有多少对$(i,j)$满足$i\in[1,a],j\in[1,b]$且$\lfloor\frac xi\rfloor j=\lfloor\frac {xj}i\rfloor$。

$$x,a,b\leq 10^9$$

题解

问题等价于求出有多少对$i,j$满足$(x\bmod i)\times j<i$。

将这个式子改写一下

$$\begin{aligned} (x\bmod i)\times j<i&\Rightarrow j<\lceil\frac{i}{x\bmod i}\rceil\\ &\Rightarrow j<\lceil\frac{i}{x-\lfloor\frac xi\rfloor i}\rceil \end{aligned}$$

枚举$\lfloor\frac xi\rfloor$，可行的$i$是一段区间。

将这个值相等的$i$划分为一段，由于这个东西随着$i$增加而递增，所以每次可以二分找出这一段的结尾。

然后打一下表会发现总段数不会很多。（我也不知道为什么）

H

题意

求$(Fib_n\bmod Fib_k)\bmod 10^9+7$，$50000$组数据

$$n,k\leq 10^{18}$$

题解

我们知道

$$\begin{bmatrix}1&1\\\ 1& 0\end{bmatrix}^n=\begin{bmatrix}F_{n+1}&F_n\\\ F_n & F_{n-1}\end{bmatrix}$$

同时

$$\begin{aligned} \begin{bmatrix}1&1\\\ 1& 0\end{bmatrix}^n&=\begin{bmatrix}1&1\\\ 1& 0\end{bmatrix}^{k-1}\times \begin{bmatrix}1&1\\\ 1& 0\end{bmatrix}^{n-k+1}\\ &=\begin{bmatrix}F_k&F_{k-1}\\\ F_{k-1}& F_{k-2}\end{bmatrix}\times \begin{bmatrix}F_{n-k+2}&F_{n-k+1}\\\ F_{n-k+1}& F_{n-k}\end{bmatrix} \end{aligned}$$

观察左上角的元素，我们可以得到

$$F_{n+1}=F_kF_{n-k+2}+F_{k-1}F_{n-k+1}$$

即

$$F_n=F_kF_{n-k+1}+F_{k-1}F_{n-k}\tag{1}$$

另外，根据行列式的运算法则$\det(AB)=\det(A)\det(B)$，将第一个等式两边同时取行列式，可以得到

$$\begin{aligned} (-1)^n&=F_{n+1}F_{n-1}-F_n^2\\ &=(F_n+F_{n-1})F_{n-1}-F_n^2\\ &=F_{n-1}^2+F_nF_{n-1}-F_n^2 \end{aligned}\tag{2}$$

接下来，我们将数列的下标拓展到负数，有$F_{-n}=(-1)^{n-1}F_n$。

将$(1)$式两边同时对$F_k$取模，可以得到

$$F_n\equiv F_{k-1}F_{n-k}\pmod{F_k}$$

固定$k$，不断地用这个等式替换$F_{n-k}$，那么每次我们能将下标减去$k$，直到$n<k$。即

$$F_n\equiv F_{k-1}^{\lfloor\frac nk\rfloor}F_{n\bmod k}\pmod {F_k}$$

记$i=\lfloor\frac nk\rfloor,j=n\bmod k$，分类讨论：

• $i=2t$

  此时$F_n\equiv(F_{k-1}^2)^tF_j$，将$(2)$代入得到

  $$\begin{aligned} F_n&\equiv ((-1)^k-F_kF_{k-1}-F_k^2)^tF_j\pmod{F_k}\\ &\equiv (-1)^{kt}F_j\pmod{F_k} \end{aligned}$$

• $i=2t+1$

  此时用$(1)$式再次替换$F_j$后就变成了$i$是偶数的情况

注意到$j=n\bmod k<k$，因此问题转化为求斐波那契数列某一项的值$\bmod 10^9+7$。

I

8会