目前咕咕咕:T6 T8 以及 T5 的 魔改 Min25 。
T1
T≤5000,a,b≤109 求:
b∑i=alcm(i,b)mod109+7前缀和一下即求
n∑i=1lcm(i,b)有一种曾经卷老师教过的非常不错的推法,考虑求和 gcd 的时候可以直接转乘 φ ,
n∑i=1gcd(i,n)=n∑i=1∑k|gcd(i,n)φ(k)原因是
∑a|bφ(a)=b那么考虑这个题,我们求
bn∑i=1igcd(i,b)我们可以定义一个函数 f ,类似之前的 φ 来做
∑a|bf(a)=1bf×I={1x}f={1x}×μ然后就有
=bn∑i=1i∑d|gcd(i,b)f(d)=b∑d|bf(d)n/d∑i=1di=b∑d|bf(d)dS(nd)那么 f 到底是啥?显然 f 是个积性函数。那么有 f(1)=1 。
f(p)+f(1)=1pf(p2)+f(p)+f(1)=1p2有
f(p)=1p−1f(pk)=1pk−1pk−1=1pk(1−p)f(n)=1n(1−p1)(1−p2)⋯复杂度 O(T√n) 。
T2
1≤a≤b≤1010 求:
b∑i=a1ii∑j=1lcm(i,j)显然可以拆前缀和。于是就成了
n∑i=11ii∑j=1lcm(i,j)=n∑i=1i∑j=1jgcd(i,j)=n∑i=1i∑j=1n∑t=1[gcd(i,j)=t]jt=n∑t=11tn∑i=1i∑j=1[gcd(i,j)=t]j=n∑t=1n/t∑i=1i∑j=1[gcd(i,j)=t]j然后考虑
n∑i=1[gcd(i,n)=1]i=n∑i=0[gcd(i,n)=1]i−[n=1]然后暂时不管后面那个 [n=1] ,显然可以枚举一下 (n−i) ,而且由于 gcd(i,n)=gcd(n−i,i) ,所以有
=n∑i=0[gcd(i,n)=1](n−i)然后两式相加,有
=nφ(n)+[n=1]2所以继续推,就是
12(n+n∑t=1n/t∑i=1iφ(i))后面那坨东西显然是可以杜教筛的,具体来说,我们有
∑pq=iφ(p)=i∑pq=ipφ(p)q=i2然后可以方便地求出 n/t 处的值。
T3
n≤1012 求:
n∑i=1∑d|igcd(d,id)=n∑i=1∑d|i∑k|gcd(d,id)φ(k)=n∑k=1φ(k)G(k)其中 G(k) 表示统计有多少对 (i,d) 满足 d|i,k|d,k|id 。
因为 d 是 k 的倍数可以考虑枚举 d ,那么 i 的限制即是 kd|i 。
n∑k=1φ(k)n/k∑d=1⌊ndk2⌋这个东西的时间复杂度是什么?显然当 k>√n 的时候是没有值的。那么 k 只需要枚举到 √n ,后面这个东西可以考虑对 nk2 来数论分块,复杂度即是
√n∑k=1√nk2=O(√nlogn)对于后面的东西,按照 nk 记忆化即可做到 O(√n) 。
T4
仔细考虑这个 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)那么我们要计算的就是
n∑i=1∑d2|iφ(d)=√n∑d=1φ(d)⌊nd2⌋于是复杂度就是 O(√n) 了。
然后这题还有一个更 NB 的做法(同时让我第一次学了学 Powerful Number)。在 这里 写了一下。
T5
显然的,设 f(x) 为 x 除以 x 的最小质因子,那么原题即求
n∑i=1n∑j=1f(gcd(i,j))k=n∑t=1f(t)kn/d∑i=1n/d∑j=1[gcd(i,j)=1]=n∑t=1f(t)k(n/d∑i=1(2φ(i))−1)后面这部分,显然是可以一次杜教筛解决的。
考虑前面这个东西怎么解决。考虑 f 的定义,是一个数除以它的最小质因子,
这个可以魔改 Min_25 筛来解决。具体来说,将记录答案的时候添加一维 0/1 表示是否已经除过了最小质因子。具体实现细节等以后写题再补吧(
T7
给定 x,a,b ,求 (i,j) 对数满足
1 | i <= a && j <= b && x / i * j == x * j / i |
T≤20,x,a,b≤109
显然这个得把下取整转取模
a∑i=1b∑j=1[jx−xmodii=xj−xjmodii]a∑i=1b∑j=1[j(xmodi)=xjmodi]a∑i=1b∑j=1[j(xmodi)<i]a∑i=1min{⌈ixmodi⌉−1,b}如果 i>x ,就算的是
a∑i=x+1min{⌈ix⌉−1,b}显然算一下哪个位置前面小于 b 即可。
否则算的就是
x∑i=1min{⌈ix−⌊xi⌋i⌉,b}我们考虑根据 ⌊xi⌋ 和外面的 ⌈ix−⌊xi⌋i⌉ 的值的改变来进行分块。打表会发现 x=109 仅有约 7×105 段。因此可以通过本题。
详细证明可以见官方题解。