0%

2.18数论

A

题意

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

题解

求出$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

题意

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

题解

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

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

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

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

C

题意

题解

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

D

题意

题解

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

E

题意

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

定义

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

题解

有两种做法。

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

它等价于

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

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

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

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

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

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

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

同时,$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$。

题解

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

那么问题等价于

第二个$\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$个质数的所有数的答案之和。

那么有

当$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$。

题解

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

将这个式子改写一下

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

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

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

H

题意

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

题解

我们知道

同时

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

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

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

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

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

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

  • $i=2t$

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

  • $i=2t+1$

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

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

I

image.png

8会