[51Nod 1238] 最小公倍数之和 (恶心杜教筛) 杜教筛

题目描述求 ∑ i = 1 N ∑ j = 1 N l c m ( i , j ) \sum_{i=1}^N\sum_{j=1}^Nlcm(i,j) i=1∑N?j=1∑N?lcm(i,j)
2 < = N < = 1 0 10 2<=N<=10^{10} 2<=N<=1010
题目分析这道题题面跟[bzoj 2693] jzptab & [bzoj 2154] Crash的数字表格一样,然而数据范围加强到了 1 0 10 10^{10} 1010,莫比乌斯反演不行了了,所以我们看看怎样玄学杜教筛
A n s = ∑ i = 1 n ∑ j = 1 n l c m ( i , j ) = 2 ∑ i = 1 n ∑ j = 1 i l c m ( i , j ) ? n ( n + 1 ) 2 L e ts ( n ) = ∑ i = 1 n ∑ j = 1 i l c m ( i , j ) , f ( n ) = ∑ i = 1 n l c m ( i , n ) ∴ f ( n ) = ∑ i = 1 n i n ( i , n ) = n ∑ i = 1 n i ( i , n ) = n ∑ d ∣ n ∑ i = 1 n [ ( i , n ) = = d ] i d = n ∑ d ∣ n ∑ i = 1 n d [ ( i , n d ) = = 1 ] i = n ∑ d ∣ n ∑ i = 1 d [ ( i , d ) = = 1 ] i = n ∑ d ∣ n φ ( d ) d + [ d = = 1 ] 2 \large Ans=\sum_{i=1}^n\sum_{j=1}^nlcm(i,j)=2\sum_{i=1}^n\sum_{j=1}^ilcm(i,j)-\frac{n(n+1)}{2}\\Let~s(n)=\sum_{i=1}^n\sum_{j=1}^ilcm(i,j),f(n)=\sum_{i=1}^nlcm(i,n)\\ \therefore f(n)=\sum_{i=1}^n\frac{in}{(i,n)}=n\sum_{i=1}^n\frac i{(i,n)}\\=n\sum_{d|n}\sum_{i=1}^n[(i,n)==d]\frac id\\=n\sum_{d|n}\sum_{i=1}^{\frac nd}[(i,\frac nd)==1]i\\=n\sum_{d|n}\sum_{i=1}^d[(i,d)==1]i\\=n\sum_{d|n}\frac{\varphi(d)d+[d==1]}2 Ans=i=1∑n?j=1∑n?lcm(i,j)=2i=1∑n?j=1∑i?lcm(i,j)?2n(n+1)?Let s(n)=i=1∑n?j=1∑i?lcm(i,j),f(n)=i=1∑n?lcm(i,n)∴f(n)=i=1∑n?(i,n)in?=ni=1∑n?(i,n)i?=nd∣n∑?i=1∑n?[(i,n)==d]di?=nd∣n∑?i=1∑dn??[(i,dn?)==1]i=nd∣n∑?i=1∑d?[(i,d)==1]i=nd∣n∑?2φ(d)d+[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 \large \sum_{i=1}^ni[(i,n)==1]=\frac {\varphi(n)n+[n==1]}2 ∑i=1n?i[(i,n)==1]=2φ(n)n+[n==1]?

继续
∴ f ( n ) = n ? 1 + ∑ d ∣ n φ ( d ) d 2 s ( n ) = ∑ i = 1 n f ( i ) = ∑ i = 1 n i ( 1 + ∑ d ∣ i φ ( d ) d ) 2 = n ( n + 1 ) 2 + ∑ i = 1 n i ∑ d ∣ i φ ( d ) d 2 = n ( n + 1 ) 2 + ∑ d = 1 n φ ( d ) d ∑ d ∣ i i 2 = n ( n + 1 ) 2 + ∑ d = 1 n φ ( d ) d 2 ∑ i = 1 ? n d ? i 2 = n ( n + 1 ) 2 + ∑ i = 1 n i ∑ d = 1 ? n i ? φ ( d ) d 2 2 A n s = 2 s ( n ) ? n ( n + 1 ) 2 = ∑ i = 1 n i ∑ d = 1 ? n i ? φ ( d ) d 2 L e th ( d ) = φ ( d ) d 2 , g ( n ) = ∑ d = 1 n h ( d ) n = ∑ d ∣ n φ ( d ) n 3 = ∑ d ∣ n φ ( d ) n 2 = ∑ d ∣ n φ ( d ) d 2 ( n d ) 2 = ∑ d ∣ n h ( d ) ( n d ) 2 ∑ i = 1 n i 3 = ∑ i = 1 n ∑ d ∣ i h ( d ) ( i d ) 2 = ∑ d = 1 n h ( d ) ∑ d ∣ i ( i d ) 2 = ∑ d = 1 n h ( d ) ∑ i = 1 ? n d ? i 2 = ∑ i = 1 n i 2 ∑ d = 1 ? n i ? h ( d ) = ∑ i = 1 n i 2 g ( ? n i ? ) g ( n ) = ∑ i = 1 n i 3 ? ∑ i = 2 n i 2 g ( ? n i ? ) = ( n ( n + 1 ) 2 ) 2 ? ∑ i = 2 n i 2 g ( ? n i ? ) \large \therefore f(n)=n\cdot\frac {1+\sum_{d|n}\varphi(d)d}2\\s(n)=\sum_{i=1}^nf(i)=\frac{\sum_{i=1}^ni(1+\sum_{d|i}\varphi(d)d)}2\\=\frac{\frac{n(n+1)}2+\sum_{i=1}^ni\sum_{d|i}\varphi(d)d}2\\=\frac{\frac{n(n+1)}2+\sum_{d=1}^n\varphi(d)d\sum_{d|i}i}2\\=\frac{\frac{n(n+1)}2+\sum_{d=1}^n\varphi(d)d^2\sum_{i=1}^{\lfloor\frac nd\rfloor}i}2\\=\frac{\frac{n(n+1)}2+\sum_{i=1}^ni\sum_{d=1}^{\lfloor\frac ni\rfloor}\varphi(d)d^2}2\\Ans=2s(n)-\frac{n(n+1)}2=\sum_{i=1}^ni\sum_{d=1}^{\lfloor\frac ni\rfloor}\varphi(d)d^2\\Let~h(d)=\varphi(d)d^2,g(n)=\sum_{d=1}^nh(d)\\n=\sum_{d|n}\varphi(d)\\n^3=\sum_{d|n}\varphi(d)n^2\\=\sum_{d|n}\varphi(d)d^2(\frac nd)^2\\=\sum_{d|n}h(d)(\frac nd)^2\\\sum_{i=1}^ni^3=\sum_{i=1}^n\sum_{d|i}h(d)(\frac id)^2\\=\sum_{d=1}^nh(d)\sum_{d|i}(\frac id)^2\\=\sum_{d=1}^nh(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}i^2\\=\sum_{i=1}^ni^2\sum_{d=1}^{\lfloor\frac ni\rfloor}h(d)\\=\sum_{i=1}^ni^2g(\lfloor\frac ni\rfloor)\\g(n)=\sum_{i=1}^ni^3-\sum_{i=2}^ni^2g(\lfloor\frac ni\rfloor)\\=(\frac{n(n+1)}2)^2-\sum_{i=2}^ni^2g(\lfloor\frac ni\rfloor) ∴f(n)=n?21+∑d∣n?φ(d)d?s(n)=i=1∑n?f(i)=2∑i=1n?i(1+∑d∣i?φ(d)d)?=22n(n+1)?+∑i=1n?i∑d∣i?φ(d)d?=22n(n+1)?+∑d=1n?φ(d)d∑d∣i?i?=22n(n+1)?+∑d=1n?φ(d)d2∑i=1?dn???i?=22n(n+1)?+∑i=1n?i∑d=1?in???φ(d)d2?Ans=2s(n)?2n(n+1)?=i=1∑n?id=1∑?in???φ(d)d2Let h(d)=φ(d)d2,g(n)=d=1∑n?h(d)n=d∣n∑?φ(d)n3=d∣n∑?φ(d)n2=d∣n∑?φ(d)d2(dn?)2=d∣n∑?h(d)(dn?)2i=1∑n?i3=i=1∑n?d∣i∑?h(d)(di?)2=d=1∑n?h(d)d∣i∑?(di?)2=d=1∑n?h(d)i=1∑?dn???i2=i=1∑n?i2d=1∑?in???h(d)=i=1∑n?i2g(?in??)g(n)=i=1∑n?i3?i=2∑n?i2g(?in??)=(2n(n+1)?)2?i=2∑n?i2g(?in??)然后就是杜教筛的形式了,上杜教筛即可.先预处理出小范围的 g g g然后较大的就用杜教筛计算
又 A n s = ∑ i = 1 n i ? g ( ? n i ? ) \large Ans=\sum_{i=1}^ni\cdot g(\lfloor\frac ni\rfloor) Ans=∑i=1n?i?g(?in??)
【[51Nod 1238] 最小公倍数之和 (恶心杜教筛)】因为 g g g函数求解时是用的记忆化,所以在外面套上一层分块优化不会影响 g g g函数的时间复杂度,所以复杂度为 Θ ( n 2 3 ) \Theta(n^{\frac 23}) Θ(n32?)
AC code

#include #include #include #include using namespace std; typedef long long LL; const int mod = 1e9+7; const int MAXN = 5e6+1; const int inv2 = 500000004; const int inv3 = 333333336; map G; LL g[MAXN]; int Prime[MAXN], Cnt, phi[MAXN]; bool IsnotPrime[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 * i % mod) % mod; }inline LL sum2(LL i) { return (i%mod) * ((i+1)%mod) % mod * ((2*i+1)%mod) % mod * inv2 % mod * inv3 % mod; }inline LL calc(LL n) { if(n < MAXN) return g[n]; if(G.count(n)) return G[n]; LL ret = (n%mod) * ((n+1)%mod) % mod * inv2 % mod; ret = ret * ret % mod; for(LL i = 2, j; i <= n; i=j+1) { j = n/(n/i); ret = (ret - (sum2(j)-sum2(i-1)) % mod * calc(n/i) % mod) % mod; } return G[n] = ret; }inline LL sum(LL i, LL j) { return ((i+j)%mod) * ((j-i+1)%mod) % mod * inv2 % mod; }inline LL solve(LL n) { LL ret = 0; for(LL i = 1, j; i <= n; i=j+1) { j = n/(n/i); ret = (ret + sum(i, j) * calc(n/i) % mod) % mod; } return ret; } int main () { init(); LL n; scanf("%lld", &n); printf("%lld\n", (solve(n)+mod)%mod); }