目前咕咕咕:T6 T8 以及 T5 的 魔改 Min25 。
T1
T≤5000,a,b≤109 求:
i=a∑blcm(i,b)mod109+7
前缀和一下即求
i=1∑nlcm(i,b)
有一种曾经卷老师教过的非常不错的推法,考虑求和 gcd 的时候可以直接转乘 φ ,
i=1∑ngcd(i,n)=i=1∑nk∣gcd(i,n)∑φ(k)
原因是
a∣b∑φ(a)=b
那么考虑这个题,我们求
bi=1∑ngcd(i,b)i
我们可以定义一个函数 f ,类似之前的 φ 来做
a∣b∑f(a)=b1f×I={x1}f={x1}×μ
然后就有
=bi=1∑nid∣gcd(i,b)∑f(d)=bd∣b∑f(d)i=1∑n/ddi=bd∣b∑f(d)dS(dn)
那么 f 到底是啥?显然 f 是个积性函数。那么有 f(1)=1 。
f(p)+f(1)=p1f(p2)+f(p)+f(1)=p21
有
f(p)=p1−1f(pk)=pk1−pk−11=pk1(1−p)f(n)=n1(1−p1)(1−p2)⋯
复杂度 O(Tn) 。
T2
1≤a≤b≤1010 求:
i=a∑bi1j=1∑ilcm(i,j)
显然可以拆前缀和。于是就成了
====i=1∑ni1j=1∑ilcm(i,j)i=1∑nj=1∑igcd(i,j)ji=1∑nj=1∑it=1∑n[gcd(i,j)=t]tjt=1∑nt1i=1∑nj=1∑i[gcd(i,j)=t]jt=1∑ni=1∑n/tj=1∑i[gcd(i,j)=t]j
然后考虑
=i=1∑n[gcd(i,n)=1]ii=0∑n[gcd(i,n)=1]i−[n=1]
然后暂时不管后面那个 [n=1] ,显然可以枚举一下 (n−i) ,而且由于 gcd(i,n)=gcd(n−i,i) ,所以有
=i=0∑n[gcd(i,n)=1](n−i)
然后两式相加,有
=2nφ(n)+[n=1]
所以继续推,就是
21⎝⎛n+t=1∑ni=1∑n/tiφ(i)⎠⎞
后面那坨东西显然是可以杜教筛的,具体来说,我们有
pq=i∑φ(p)=ipq=i∑pφ(p)q=i2
然后可以方便地求出 n/t 处的值。
T3
n≤1012 求:
==i=1∑nd∣i∑gcd(d,di)i=1∑nd∣i∑k∣gcd(d,di)∑φ(k)k=1∑nφ(k)G(k)
其中 G(k) 表示统计有多少对 (i,d) 满足 d∣i,k∣d,k∣di 。
因为 d 是 k 的倍数可以考虑枚举 d ,那么 i 的限制即是 kd∣i 。
k=1∑nφ(k)d=1∑n/k⌊dk2n⌋
这个东西的时间复杂度是什么?显然当 k>n 的时候是没有值的。那么 k 只需要枚举到 n ,后面这个东西可以考虑对 k2n 来数论分块,复杂度即是
k=1∑nk2n=O(nlogn)
对于后面的东西,按照 kn 记忆化即可做到 O(n) 。
T4
仔细考虑这个 f 的定义,不难发现实际上求的是
f(x)=∏piei/2
也就是
f(x)=g(x)
g(x) 是 x 的最大平方因子开根后的结果。
这个题的原题推法非常仙,就不写了(而且也不太可能想的到),这里写一下 lsj 秒的推法。设 u=g(x) ,那么显然对于 x 的任何平方因子 d2,一定有 d∣u ,且所有 u 的约数都一定能满足这个数的平方是 x 的因子。
于是我们考虑进行一种容斥,这个容斥计算了所有 u 的约数且最后结果整好是 u ,即
d∣u∑f(d)=u
显然 f=φ 即可。所以对于一个数有
g(x)=d2∣x∑φ(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) 了。
然后这题还有一个更 NB 的做法(同时让我第一次学了学 Powerful Number)。在 这里 写了一下。
T5
显然的,设 f(x) 为 x 除以 x 的最小质因子,那么原题即求
==i=1∑nj=1∑nf(gcd(i,j))kt=1∑nf(t)ki=1∑n/dj=1∑n/d[gcd(i,j)=1]t=1∑nf(t)k⎝⎛i=1∑n/d(2φ(i))−1⎠⎞
后面这部分,显然是可以一次杜教筛解决的。
考虑前面这个东西怎么解决。考虑 f 的定义,是一个数除以它的最小质因子,
这个可以魔改 Min_25 筛来解决。具体来说,将记录答案的时候添加一维 0/1 表示是否已经除过了最小质因子。具体实现细节等以后写题再补吧(
T7
给定 x,a,b ,求 (i,j) 对数满足
i <= a && j <= b && x / i * j == x * j / i
T≤20,x,a,b≤109
显然这个得把下取整转取模
i=1∑aj=1∑b[jix−xmodi=ixj−xjmodi]i=1∑aj=1∑b[j(xmodi)=xjmodi]i=1∑aj=1∑b[j(xmodi)<i]i=1∑amin{⌈xmodii⌉−1,b}
如果 i>x ,就算的是
i=x+1∑amin{⌈xi⌉−1,b}
显然算一下哪个位置前面小于 b 即可。
否则算的就是
i=1∑xmin{⌈x−⌊ix⌋ii⌉,b}
我们考虑根据 ⌊ix⌋ 和外面的 ⌈x−⌊ix⌋ii⌉ 的值的改变来进行分块。打表会发现 x=109 仅有约 7×105 段。因此可以通过本题。
详细证明可以见官方题解。
\