Processing math: 100%
2.18 数论题

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

T1

T5000,a,b109 求:

bi=alcm(i,b)mod109+7

前缀和一下即求

ni=1lcm(i,b)

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

ni=1gcd(i,n)=ni=1k|gcd(i,n)φ(k)

原因是

a|bφ(a)=b

那么考虑这个题,我们求

bni=1igcd(i,b)

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

a|bf(a)=1bf×I={1x}f={1x}×μ

然后就有

=bni=1id|gcd(i,b)f(d)=bd|bf(d)n/di=1di=bd|bf(d)dS(nd)

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

f(p)+f(1)=1pf(p2)+f(p)+f(1)=1p2

f(p)=1p1f(pk)=1pk1pk1=1pk(1p)f(n)=1n(1p1)(1p2)

复杂度 O(Tn)

T2

1ab1010 求:

bi=a1iij=1lcm(i,j)

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

ni=11iij=1lcm(i,j)=ni=1ij=1jgcd(i,j)=ni=1ij=1nt=1[gcd(i,j)=t]jt=nt=11tni=1ij=1[gcd(i,j)=t]j=nt=1n/ti=1ij=1[gcd(i,j)=t]j

然后考虑

ni=1[gcd(i,n)=1]i=ni=0[gcd(i,n)=1]i[n=1]

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

=ni=0[gcd(i,n)=1](ni)

然后两式相加,有

=nφ(n)+[n=1]2

所以继续推,就是

12(n+nt=1n/ti=1iφ(i))

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

pq=iφ(p)=ipq=ipφ(p)q=i2

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

T3

n1012 求:

ni=1d|igcd(d,id)=ni=1d|ik|gcd(d,id)φ(k)=nk=1φ(k)G(k)

其中 G(k) 表示统计有多少对 (i,d) 满足 d|i,k|d,k|id

因为 dk 的倍数可以考虑枚举 d ,那么 i 的限制即是 kd|i

nk=1φ(k)n/kd=1ndk2

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

nk=1nk2=O(nlogn)

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

T4

image.png

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

f(x)=pei/2i

也就是

f(x)=g(x)

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

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

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

d|uf(d)=u

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

g(x)=d2|xφ(d)

那么我们要计算的就是

ni=1d2|iφ(d)=nd=1φ(d)nd2

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

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

T5

image.png

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

ni=1nj=1f(gcd(i,j))k=nt=1f(t)kn/di=1n/dj=1[gcd(i,j)=1]=nt=1f(t)k(n/di=1(2φ(i))1)

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

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

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

T7

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

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

T20,x,a,b109

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

ai=1bj=1[jxxmodii=xjxjmodii]ai=1bj=1[j(xmodi)=xjmodi]ai=1bj=1[j(xmodi)<i]ai=1min{ixmodi1,b}

如果 i>x ,就算的是

ai=x+1min{ix1,b}

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

否则算的就是

xi=1min{ixxii,b}

我们考虑根据 xi 和外面的 ixxii 的值的改变来进行分块。打表会发现 x=109 仅有约 7×105 段。因此可以通过本题。

详细证明可以见官方题解

文章作者: yijan
文章链接: https://yijan.co/218-shu-lun-ti/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog