[51Nod 1227] 平均最小公倍数 (杜教筛) 杜教筛

题目描述 【[51Nod 1227] 平均最小公倍数 (杜教筛)】求 ∑ i = a b ∑ j = 1 i l c m ( i , j ) i \large\sum_{i=a}^b\sum_{j=1}^i\frac{lcm(i,j)}i i=a∑b?j=1∑i?ilcm(i,j)?
1 < = a < = b < = 1 0 9 1 < = a < = b < = 10^9 1<=a<=b<=109
题目分析这道题其实是[51Nod 1238] 最小公倍数之和题解的简化版,或者说是本质…
就直接上公式了
令 f ( n ) = ∑ i = 1 n l c m ( n , i ) n = ∑ i = 1 n i ( n , i ) \large f(n)=\sum_{i=1}^n\frac{lcm(n,i)}n=\sum_{i=1}^n\frac i{(n,i)} f(n)=∑i=1n?nlcm(n,i)?=∑i=1n?(n,i)i?,则 A n s = ∑ i = a b f ( i ) Ans=\sum_{i=a}^bf(i) Ans=∑i=ab?f(i)
f ( n ) = ∑ d ∣ n ∑ d ∣ i i d [ ( i , n ) = = d ] = ∑ d ∣ n ∑ d ∣ i i d [ ( i d , n d ) = = 1 ] = ∑ d ∣ n ∑ i = 1 ? n d ? i [ ( i , n d ) = = 1 ] = ∑ d ∣ n ∑ i = 1 d i [ ( i , d ) = = 1 ] \large f(n)=\sum_{d|n}\sum_{d|i}\frac id[(i,n)==d]\\=\sum_{d|n}\sum_{d|i}\frac id[(\frac id,\frac nd)==1]\\=\sum_{d|n}\sum_{i=1}^{\lfloor\frac nd\rfloor}i[(i,\frac nd)==1]\\=\sum_{d|n}\sum_{i=1}^di[(i,d)==1] f(n)=d∣n∑?d∣i∑?di?[(i,n)==d]=d∣n∑?d∣i∑?di?[(di?,dn?)==1]=d∣n∑?i=1∑?dn???i[(i,dn?)==1]=d∣n∑?i=1∑d?i[(i,d)==1]
此处有一个常识
∑ i = 1 n i [ ( i , n ) = = 1 ] = φ ( n ) n + [ n = = 1 ] 2 \sum_{i=1}^ni[(i,n)==1]=\frac {\varphi(n)n+[n==1]}2 i=1∑n?i[(i,n)==1]=2φ(n)n+[n==1]?

证明如下
- 当 n > 1 n> 1 n>1时,若 ( i , n ) = 1   ?   ( n ? i , n ) = 1 (i,n)=1\iff(n-i,n)=1 (i,n)=1?(n?i,n)=1,所以与 n n n互质的数是成对出现,且他们的和为 n n n
- 再加之 n = 1 n=1 n=1的特殊情况,可得
  ∑ i = 1 n i [ ( i , n ) = = 1 ] = φ ( n ) n + [ n = = 1 ] 2 \sum_{i=1}^ni[(i,n)==1]=\frac {\varphi(n)n+[n==1]}2 i=1∑n?i[(i,n)==1]=2φ(n)n+[n==1]?

继续
∴ f ( n ) = ∑ d ∣ n φ ( d ) d + [ d = = 1 ] 2 = 1 + ∑ d ∣ n φ ( d ) d 2 \large \therefore f(n)=\sum_{d|n}\frac {\varphi(d)d+[d==1]}2\\=\frac{1+\sum_{d|n}\varphi(d)d}2 ∴f(n)=d∣n∑?2φ(d)d+[d==1]?=21+∑d∣n?φ(d)d?
∴ ∑ i = 1 n f ( i ) = n + ∑ i = 1 n ∑ d ∣ n φ ( d ) d 2 = n + ∑ d = 1 n φ ( d ) d ∑ d ∣ i 1 2 = n + ∑ d = 1 n φ ( d ) d ? n d ? 2 \large \therefore \sum_{i=1}^nf(i)=\frac{n+\sum_{i=1}^n\sum_{d|n}\varphi(d)d}2\\=\\\frac{n+\sum_{d=1}^n\varphi(d)d\sum_{d|i}1}2\\=\frac{n+\sum_{d=1}^n\varphi(d)d\lfloor\frac nd\rfloor}2 ∴i=1∑n?f(i)=2n+∑i=1n?∑d∣n?φ(d)d?=2n+∑d=1n?φ(d)d∑d∣i?1?=2n+∑d=1n?φ(d)d?dn???
此时就可以用整除分块优化+杜教筛计算 ∑ d = 1 n φ ( d ) d \large \sum_{d=1}^n\varphi(d)d ∑d=1n?φ(d)d
令 h ( n ) = φ ( d ) d , g ( n ) = ∑ i = 1 n h ( d ) \large h(n)=\varphi(d)d,g(n)=\sum_{i=1}^nh(d) h(n)=φ(d)d,g(n)=∑i=1n?h(d)
∵ n = ∑ d ∣ n φ ( d ) ∴ n 2 = ∑ d ∣ n φ ( d ) n = ∑ d ∣ n φ ( d ) d ? n d = ∑ d ∣ n h ( d ) n d ∴ ∑ i = 1 n i 2 = ∑ i = 1 n ∑ d ∣ i h ( d ) i d = ∑ d = 1 n h ( d ) ∑ d ∣ i i d = ∑ d = 1 n h ( d ) ∑ i = 1 ? n d ? i \large\because n=\sum_{d|n}\varphi(d)\\\therefore n^2=\sum_{d|n}\varphi(d)n=\sum_{d|n}\varphi(d)d\cdot\frac nd=\sum_{d|n}h(d)\frac nd\\\therefore \sum_{i=1}^ni^2=\sum_{i=1}^n\sum_{d|i}h(d)\frac id\\=\sum_{d=1}^nh(d)\sum_{d|i}\frac id\\=\sum_{d=1}^nh(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}i ∵n=d∣n∑?φ(d)∴n2=d∣n∑?φ(d)n=d∣n∑?φ(d)d?dn?=d∣n∑?h(d)dn?∴i=1∑n?i2=i=1∑n?d∣i∑?h(d)di?=d=1∑n?h(d)d∣i∑?di?=d=1∑n?h(d)i=1∑?dn???i
注意我们是在杜教筛,不能到这里就把 ∑ i = 1 ? n d ? i \sum_{i=1}^{\lfloor\frac nd\rfloor}i ∑i=1?dn???i看做 Θ ( 1 ) \Theta(1) Θ(1)可求的式子而之后再也不做变换,那样往往会陷入更麻烦的方法或者死胡同里去,接着往下
∴ ∑ i = 1 n i 2 = ∑ i = 1 n i ∑ d = 1 ? n i ? h ( d ) = ∑ i = 1 n i ? g ( ? n i ? ) ∴ g ( n ) = ∑ i = 1 n i 2 ? ∑ i = 2 n i ? g ( ? n i ? ) \large\therefore \sum_{i=1}^ni^2=\sum_{i=1}^ni\sum_{d=1}^{\lfloor\frac ni\rfloor}h(d)=\sum_{i=1}^ni\cdot g({\lfloor\frac ni\rfloor})\\\therefore g(n)= \sum_{i=1}^ni^2-\sum_{i=2}^ni\cdot g({\lfloor\frac ni\rfloor}) ∴i=1∑n?i2=i=1∑n?id=1∑?in???h(d)=i=1∑n?i?g(?in??)∴g(n)=i=1∑n?i2?i=2∑n?i?g(?in??)
然后套杜教筛即可
虽然在外面套了一层整除分块优化,但由于记忆化的原因,不影响时间复杂度,预处理出一部分 g g g后总复杂度为 Θ ( n 2 3 ) \large\Theta(n^{\frac 23}) Θ(n32?)
…有兴趣的可以去了解一下[51Nod 1238] 最小公倍数之和题解,比这道题恶心点
AC code

#include #include #include #include #include using namespace std; using namespace tr1; typedef long long LL; const int inv6 = 166666668; const int inv2 = 500000004; const int MAXN = 5e6 + 1; const int mod = 1e9 + 7; int Prime[MAXN], phi[MAXN], Cnt; bool IsnotPrime[MAXN]; LL g[MAXN]; void init() { phi[1] = 1; for(int i = 2; i < MAXN; ++i) { if(!IsnotPrime[i]) Prime[++Cnt] = i, phi[i] = i-1; for(int j = 1; j <= Cnt && i * Prime[j] < MAXN; ++j) { IsnotPrime[i * Prime[j]] = 1; if(i % Prime[j] == 0) { phi[i * Prime[j]] = phi[i] * Prime[j]; break; } phi[i * Prime[j]] = phi[i] * phi[Prime[j]]; } } for(int i = 1; i < MAXN; ++i) g[i] = (g[i-1] + 1ll * phi[i] * i % mod) % mod; } unordered_map G; inline LL sum1(LL i, LL j) { return ((i+j)%mod) * ((j-i+1)%mod) % mod * inv2 % mod; } inline LL sum(LL n) { if(n < MAXN) return g[n]; if(G.count(n)) return G[n]; LL ret = (n%mod) * ((n+1)%mod) % mod * ((2*n+1)%mod) % mod * inv6 % mod; for(LL i = 2, j; i <= n; i=j+1) { j = n/(n/i); ret = (ret - sum(n/i) * sum1(i, j) % mod) % mod; } return G[n]=ret; }LL solve(LL n) { LL ret = n%mod; for(LL i = 1, j; i <= n; i=j+1) { j = n/(n/i); ret = (ret + ((sum(j)-sum(i-1))%mod) * ((n/i)%mod) % mod) % mod; } return ret * inv2 % mod; }int main () { LL a, b; init(); scanf("%lld%lld", &a, &b); printf("%lld\n", ((solve(b)-solve(a-1)) % mod + mod) % mod); }