2.18 数论题

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

T1

$T\le 5000,a,b\le 10^9$ 求:

前缀和一下即求

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

原因是

那么考虑这个题,我们求

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

然后就有

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

复杂度 $O(T\sqrt n)$ 。

T2

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

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

然后考虑

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

然后两式相加,有

所以继续推,就是

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

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

T3

$n \le 10^{12}$ 求:

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

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

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

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

T4

image.png

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

也就是

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

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

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

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

那么我们要计算的就是

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

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

T5

image.png

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

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

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

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

T7

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

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

$T \le 20 , x,a,b \le 10^9$

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

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

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

否则算的就是

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

详细证明可以见官方题解

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