51Nod 1227 平均最小公倍数（杜教筛）数论

题目链接：哆啦A梦传送门
题意：
求 ∑ i = a b 1 i ∑ j = 1 i l c m ( j , i ) \begin{aligned}\sum_{i=a}^{b}\frac{1}{i}\sum_{j=1}^{i}lcm(j,i)\end{aligned} i=a∑b?i1?j=1∑i?lcm(j,i)?
我们设：
a n s = ∑ i = 1 n 1 i ∑ j = 1 i l c m ( j , i ) = ∑ i = 1 n 1 i ∑ j = 1 i i ? j g c d ( i , j ) = ∑ d = 1 n d ∑ i = 1 n d 1 i ? i ∑ j = 1 i [ g c d ( i , j ) = 1 ] j = ∑ d = 1 n d ∑ i = 1 n d i ? φ ( i ) + [ n = = 1 ] 2 = ( 1 2 ∑ d = 1 n d ∑ i = 1 n d i ? φ ( i ) ) + n 2 \begin{aligned}ans& =\sum_{i=1}^{n}\frac{1}{i}\sum_{j=1}^{i}lcm(j,i)\\ & =\sum_{i=1}^{n}\frac{1}{i}\sum_{j=1}^{i}\frac{i*j}{gcd(i,j)}\\ & =\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}\frac{1}{i}*i\sum_{j=1}^{i}[gcd(i,j)=1]j\\ & =\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}\frac{i*\varphi(i)+[n==1]}{2}\\ & =(\frac{1}{2}\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}i*\varphi(i))+\frac{n}{2}\end{aligned} ans?=i=1∑n?i1?j=1∑i?lcm(j,i)=i=1∑n?i1?j=1∑i?gcd(i,j)i?j?=d=1∑n?di=1∑dn??i1??ij=1∑i?[gcd(i,j)=1]j=d=1∑n?di=1∑dn??2i?φ(i)+[n==1]?=(21?d=1∑n?di=1∑dn??i?φ(i))+2n??
现在我们看到这个式子，只需分块计算，但我们还得快速得出 ∑ i = 1 n i ? φ ( i ) \begin{aligned}\sum_{i=1}^{n}i*\varphi(i)\end{aligned} i=1∑n?i?φ(i)?
我们知道有一个关于 φ ( i ) \varphi(i) φ(i)的性质：
n = ∑ d ∣ n φ ( d ) n=\sum_{d|n}\varphi(d) n=∑d∣n?φ(d)
那么我们设 h ( x ) = x ? φ ( x ) h(x)=x*\varphi(x) h(x)=x?φ(x)， S ( n ) = ∑ i = 1 n h ( i ) S(n)=\sum_{i=1}^{n}h(i) S(n)=∑i=1n?h(i)
我们知道： ∑ i = 1 n i 2 = n ? ( n + 1 ) ? ( 2 ? n + 1 ) 6 \sum_{i=1}^{n}i^2=\frac{n*(n+1)*(2*n+1)}{6} ∑i=1n?i2=6n?(n+1)?(2?n+1)?
即：
∑ i = 1 n i 2 = ∑ d = 1 n ∑ i ∣ d φ ( i ) ? d = ∑ d = 1 n ∑ i ∣ d h ( i ) ? d i = ∑ d = 1 n ∑ i = 1 n d h ( i ) ? ( d ? i ) i = ∑ d = 1 n d ∑ i = 1 n d h ( i ) \begin{aligned}\sum_{i=1}^{n}i^2& =\sum_{d=1}^{n}\sum_{i|d}\varphi(i)*d\\ & =\sum_{d=1}^{n}\sum_{i|d}h(i)*\frac{d}{i}\\ & =\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{d}}h(i)*\frac{(d*i)}{i}\\ & =\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}h(i)\end{aligned} i=1∑n?i2?=d=1∑n?i∣d∑?φ(i)?d=d=1∑n?i∣d∑?h(i)?id?=d=1∑n?i=1∑dn??h(i)?i(d?i)?=d=1∑n?di=1∑dn??h(i)?
即：
n ? ( n + 1 ) ? ( 2 ? n + 1 ) 6 = S ( n ) + ∑ d = 2 n d ∑ i = 1 n d h ( i ) \begin{aligned}\frac{n*(n+1)*(2*n+1)}{6}=S(n)+\sum_{d=2}^{n}d\sum_{i=1}^{\frac{n}{d}}h(i)\end{aligned} 6n?(n+1)?(2?n+1)?=S(n)+d=2∑n?di=1∑dn??h(i)?
S ( n ) = n ? ( n + 1 ) ? ( 2 ? n + 1 ) 6 ? ∑ d = 2 n d ∑ i = 1 n d h ( i ) \begin{aligned}S(n)=\frac{n*(n+1)*(2*n+1)}{6}-\sum_{d=2}^{n}d\sum_{i=1}^{\frac{n}{d}}h(i)\end{aligned} S(n)=6n?(n+1)?(2?n+1)??d=2∑n?di=1∑dn??h(i)?
故我们可以预处理前6000000现 x ? φ ( x ) x*\varphi(x) x?φ(x)和。再分块计算就好了。

#include #include #include #includeusing namespace std; typedef long long LL; const LL mod=1000000007; const int N=6e6; LL sum[N]; ///存放S的前N项 bool vis[N+10]; LL phi[N+10]; int pri[N+10],tot; tr1::unordered_map w; LL inv2,inv4,inv6; void init() {phi[1]=1; for(int i=2; i<=N; i++) { if(!vis[i]){ phi[i]=i-1; pri[++tot]=i; } for(int j=1; j<=tot&&i*pri[j]<=N; j++) { int t=pri[j]; vis[i*t]=1; if(i%t==0){ phi[i*t]=phi[i]*t; break; } phi[i*t]=phi[i]*(t-1); } }///预处理 \sum_{i=1}^{N}i*phi[i] for(int i=1; i<=N; i++) { sum[i]=(sum[i-1]+1LL*phi[i]%mod*i%mod)%mod; }}LL fast_pow(LL a1,LL n) { LL ans=1; while(n) { if(n&1) ans=ans*a1%mod; a1=a1*a1%mod; n>>=1; } return ans; }LL s2(LL x) ///\sum_{i=1}^{x}i*i { LL t=x%mod; return t*(t+1)%mod*(2*t+1)%mod*inv6%mod; }LL s1(LL x) ///\sum_{i=1}^{x}i { x=x%mod; return x*(x+1)%mod*inv2%mod; }LL djs(LL x) { if(x<=N) return sum[x]; if(w[x]) return w[x]; LL t=x%mod; LL ans=s2(x); for(LL l=2,r; l<=x; l=r+1) { r=x/(x/l); ans=(ans-(s1(r)-s1(l-1)+mod)%mod*djs(x/l)+mod)%mod; }return w[x]=ans; }LL solve(LL n) {LL ans=n%mod; for(LL l=1,r; l<=n; l=r+1) { r=n/(n/l); ans=(ans+(r-l+1+mod)%mod*djs(n/l)%mod)%mod; }return ans*inv2%mod; }int main() {LL n; inv2=fast_pow((LL)2,mod-2); inv4=fast_pow((LL)4,mod-2); inv6=fast_pow((LL)6,mod-2); init(); LL a,b; scanf("%lld%lld",&a,&b); LL ans=0; ans=(solve(b)-solve(a-1)+mod)%mod; printf("%lld\n",ans); return 0; }

【51Nod 1227 平均最小公倍数（杜教筛）】 \begin{aligned}\end{aligned}