2.18 数论题

目前咕咕咕:T6 T8 以及 T5 的 魔改 Min25 。

T1

T5000,a,b109T\le 5000,a,b\le 10^9 求:

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

前缀和一下即求

i=1nlcm(i,b)\sum_{i=1}^n \text{lcm}(i,b)

有一种曾经卷老师教过的非常不错的推法,考虑求和 gcd\gcd 的时候可以直接转乘 φ\varphi

i=1ngcd(i,n)=i=1nkgcd(i,n)φ(k)\begin{aligned} & \sum_{i=1}^n \gcd(i,n)\\ &= \sum_{i=1}^n \sum_{k|\gcd(i,n)} \varphi(k) \end{aligned}

原因是

abφ(a)=b\sum_{a|b} \varphi(a) = b

那么考虑这个题,我们求

bi=1nigcd(i,b)b\sum_{i=1}^n \frac{i}{\gcd(i,b)}

我们可以定义一个函数 ff ,类似之前的 φ\varphi 来做

abf(a)=1bf×I={1x}f={1x}×μ\sum_{a|b} f(a) = \frac 1 b\\ f \times I = \{\frac 1 x\}\\ f = \{\frac 1 x\} \times \mu

然后就有

=bi=1nidgcd(i,b)f(d)=bdbf(d)i=1n/ddi=bdbf(d)dS(nd)\begin{aligned} &=b \sum_{i=1}^n i \sum_{d | \gcd(i,b)} f(d)\\ &=b\sum_{d|b} f(d) \sum_{i=1}^{n/d} di\\ &= b\sum_{d|b} f(d)d S(\frac n d) \end{aligned}

那么 ff 到底是啥?显然 ff 是个积性函数。那么有 f(1)=1f(1) = 1

f(p)+f(1)=1pf(p2)+f(p)+f(1)=1p2f(p) + f(1) = \frac 1 p\\ f(p^2) + f(p) + f(1) = \frac 1 {p^2}

f(p)=1p1f(pk)=1pk1pk1=1pk(1p)f(n)=1n(1p1)(1p2)f(p) = \frac 1 p - 1\\ f(p^k) = \frac{1}{p^k} - \frac{1}{p^{k-1}} = \frac{1}{p^k}(1-p)\\ f(n) = \frac 1 n (1-p_1)(1-p_2) \cdots

复杂度 O(Tn)O(T\sqrt n)

T2

1ab10101 \le a \le b \le 10^{10} 求:

i=ab1ij=1ilcm(i,j)\sum_{i=a}^b \frac 1 i \sum_{j=1}^i \text{lcm}(i,j)

显然可以拆前缀和。于是就成了

i=1n1ij=1ilcm(i,j)=i=1nj=1ijgcd(i,j)=i=1nj=1it=1n[gcd(i,j)=t]jt=t=1n1ti=1nj=1i[gcd(i,j)=t]j=t=1ni=1n/tj=1i[gcd(i,j)=t]j\begin{aligned} &\sum_{i=1}^n \frac 1 i \sum_{j=1}^i \text{lcm}(i,j)\\ =&\sum_{i=1}^n \sum_{j=1}^i \frac j {\gcd(i,j)}\\ =&\sum_{i=1}^n \sum_{j=1}^i \sum_{t=1}^n [\gcd(i,j) = t] \frac j {t}\\ =&\sum_{t=1}^n \frac 1 t \sum_{i=1}^n \sum_{j=1}^i [\gcd(i,j) = t] j\\ =&\sum_{t=1}^n \sum_{i=1}^{n/t} \sum_{j=1}^i [\gcd(i,j) = t] j\\ \end{aligned}

然后考虑

i=1n[gcd(i,n)=1]i=i=0n[gcd(i,n)=1]i[n=1]\begin{aligned} &\sum_{i=1}^n [\gcd(i,n) = 1] i\\ =& \sum_{i=0}^n [\gcd(i,n) = 1] i - [n=1] \end{aligned}

然后暂时不管后面那个 [n=1][n=1] ,显然可以枚举一下 (ni)(n-i) ,而且由于 gcd(i,n)=gcd(ni,i)\gcd(i,n) = \gcd(n-i,i) ,所以有

=i=0n[gcd(i,n)=1](ni)= \sum_{i=0}^n [\gcd(i,n) = 1] (n-i)

然后两式相加,有

=nφ(n)+[n=1]2= \frac{n\varphi(n) + [n=1]}{2}

所以继续推,就是

12(n+t=1ni=1n/tiφ(i))\frac 1 2\left(n+\sum_{t=1}^n \sum_{i=1}^{n/t} i\varphi(i)\right)

后面那坨东西显然是可以杜教筛的,具体来说,我们有

pq=iφ(p)=ipq=ipφ(p)q=i2\sum_{pq = i} \varphi(p) = i\\ \sum_{pq=i} p\varphi(p) q = i^2

然后可以方便地求出 n/tn/t 处的值。

T3

n1012n \le 10^{12} 求:

i=1ndigcd(d,id)=i=1ndikgcd(d,id)φ(k)=k=1nφ(k)G(k)\begin{aligned} &\sum_{i=1}^n \sum_{d|i}\gcd(d,\frac i d)\\ =&\sum_{i=1}^n \sum_{d|i} \sum_{k|\gcd(d,\frac i d)} \varphi(k)\\ =&\sum_{k=1}^n \varphi(k) G(k) \end{aligned}

其中 G(k)G(k) 表示统计有多少对 (i,d)(i,d) 满足 di,kd,kidd|i,k|d,k|\frac i d

因为 ddkk 的倍数可以考虑枚举 dd ,那么 ii 的限制即是 kdikd | i

k=1nφ(k)d=1n/kndk2\sum_{k=1}^n \varphi(k) \sum_{d=1}^{n/k} \lfloor \frac n {dk^2} \rfloor

这个东西的时间复杂度是什么?显然当 k>nk > \sqrt n 的时候是没有值的。那么 kk 只需要枚举到 n\sqrt n ,后面这个东西可以考虑对 nk2\frac{n}{k^2} 来数论分块,复杂度即是

k=1nnk2=O(nlogn)\sum_{k=1}^{\sqrt n} \sqrt{\frac{n}{k^2}} = O(\sqrt n \log n)

对于后面的东西,按照 nk\frac n k 记忆化即可做到 O(n)O(\sqrt n)

T4

image.png

仔细考虑这个 ff 的定义,不难发现实际上求的是

f(x)=piei/2f(x) = \prod p_i^{e_i/2}

也就是

f(x)=g(x)f(x) = g(x)\\

g(x)g(x)xx 的最大平方因子开根后的结果。

这个题的原题推法非常仙,就不写了(而且也不太可能想的到),这里写一下 lsj 秒的推法。设 u=g(x)u = g(x) ,那么显然对于 xx 的任何平方因子 d2d^2,一定有 dud|u ,且所有 uu 的约数都一定能满足这个数的平方是 xx 的因子。

于是我们考虑进行一种容斥,这个容斥计算了所有 uu 的约数且最后结果整好是 uu ,即

duf(d)=u\sum_{d | u} f(d) = u

显然 f=φf = \varphi 即可。所以对于一个数有

g(x)=d2xφ(d)g(x) = \sum_{d^2 | x} \varphi(d)

那么我们要计算的就是

\sum_{i=1}^n \sum_{d^2|i} \varphi(d)\\ = \sum_{d=1}^\sqrt n \varphi(d) \lfloor\frac{n}{d^2}\rfloor

于是复杂度就是 O(n)O(\sqrt n) 了。

然后这题还有一个更 NB 的做法(同时让我第一次学了学 Powerful Number)。在 这里 写了一下。

T5

image.png

显然的,设 f(x)f(x)xx 除以 xx 的最小质因子,那么原题即求

i=1nj=1nf(gcd(i,j))k=t=1nf(t)ki=1n/dj=1n/d[gcd(i,j)=1]=t=1nf(t)k(i=1n/d(2φ(i))1)\begin{aligned} &\sum_{i=1}^n \sum_{j=1}^n f(\gcd(i,j))^k\\ =&\sum_{t=1}^n f(t)^k \sum_{i=1}^{n/d} \sum_{j=1}^{n/d} [\gcd(i,j) = 1]\\ =&\sum_{t=1}^n f(t)^k \left(\sum_{i=1}^{n/d} (2\varphi(i)) - 1\right) \end{aligned}

后面这部分,显然是可以一次杜教筛解决的。

考虑前面这个东西怎么解决。考虑 ff 的定义,是一个数除以它的最小质因子,

这个可以魔改 Min_25 筛来解决。具体来说,将记录答案的时候添加一维 0/10/1 表示是否已经除过了最小质因子。具体实现细节等以后写题再补吧(

T7

给定 x,a,bx,a,b ,求 (i,j)(i,j) 对数满足

i <= a && j <= b && x / i * j == x * j / i

T20,x,a,b109T \le 20 , x,a,b \le 10^9

显然这个得把下取整转取模

i=1aj=1b[jxxmodii=xjxjmodii]i=1aj=1b[j(xmodi)=xjmodi]i=1aj=1b[j(xmodi)<i]i=1amin{ixmodi1,b}\sum_{i=1}^a \sum_{j=1}^b [j\frac{x - x\bmod i}{i} = \frac{xj - xj \bmod i}{i}]\\ \sum_{i=1}^a \sum_{j=1}^b [j(x\bmod i) = xj \bmod i]\\ \sum_{i=1}^a \sum_{j=1}^b [j(x \bmod i) < i]\\ \sum_{i=1}^a \min\{\lceil \frac i {x \bmod i}\rceil - 1,b\}

如果 i>xi > x ,就算的是

i=x+1amin{ix1,b}\sum_{i=x+1}^a \min\{\lceil \frac i x\rceil - 1 , b\}

显然算一下哪个位置前面小于 bb 即可。

否则算的就是

i=1xmin{ixxii,b}\sum_{i=1}^x \min\{\lceil \frac i {x - \lfloor\frac x i\rfloor i} \rceil,b\}

我们考虑根据 xi\lfloor \frac x i \rfloor 和外面的 ixxii\lceil \frac i {x - \lfloor\frac x i\rfloor i} \rceil 的值的改变来进行分块。打表会发现 x=109x=10^9 仅有约 7×1057\times 10^5 段。因此可以通过本题。

详细证明可以见官方题解

\