1 条题解
-
0
问题
给出 ，求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m i*j*\gcd(i,j)$ 。
题解
设 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m i*j*\gcd(i,j)$ 222 $=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \sum\limits_{d=1}^n i*j*d \lbrack\gcd(i,j)=d\rbrack$ 333 $=\sum\limits_{d=1}^n \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}} id*jd*d \lbrack\gcd(i,j)=1\rbrack$ 444 $=\sum\limits_{d=1}^n d^3 \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}} i * j\lbrack\gcd(i,j)=1\rbrack$ 555 $=\sum\limits_{d=1}^n d^3 \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}i * j\sum\limits_{a | \gcd(i,j)}\mu(a)$ 666 $=\sum\limits_{d=1}^n d^3 \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}i * j\sum\limits_{a=1}^{\frac{n}{d}} \lbrack a | i \rbrack \lbrack a | j \rbrack \mu(a)$ 注意： 的上限是 $=\sum\limits_{d=1}^n d^3 \sum\limits_{a=1}^{\frac{n}{d}}\mu(a)\sum\limits_{i=1}^{\frac{n}{d}}i*\lbrack a | i \rbrack\sum\limits_{j=1}^{\frac{m}{d}}j*\lbrack a | j \rbrack$ 观察 $\sum\limits_{i=1}^{\frac{n}{d}}i*\lbrack a | i \rbrack$ ，联想 $\sum\limits_{i=1}^n \lbrack a | i \rbrack = \lfloor \frac{n}{a} \rfloor$
故：$\sum\limits_{i=1}^{\frac{n}{d}}i*\lbrack a | i \rbrack$$=\sum\limits_{d=1}^n d^3 \sum\limits_{a=1}^{\frac{n}{d}}a^2\mu(a)\sum\limits_{i=1}^{\frac{n}{ad}}i\sum\limits_{j=1}^{\frac{m}{ad}}j$ 设： $=\sum\limits_{d=1}^n d^3 \sum\limits_{a=1}^{\frac{n}{d}}a^2\mu(a)S(\lfloor \frac{n}{ad} \rfloor) S(\lfloor \frac{m}{ad} \rfloor)$ 设： $=\sum\limits_{d=1}^n d \sum\limits_{\frac{T}{d}=1}^{\frac{n}{d}} T^2 \mu(\frac{T}{d})S(\lfloor \frac{n}{T} \rfloor)S(\lfloor \frac{m}{T} \rfloor)$ 777 $=\sum\limits_{d=1}^n d \sum\limits_{T=1}^n T^2 \mu(\frac{T}{d}) S(\lfloor \frac{n}{T} \rfloor)S(\lfloor \frac{m}{T} \rfloor)$ 888 $= \sum\limits_{T=1}^n T^2 \sum\limits_{d=1}^n d \mu(\frac{T}{d}) S(\lfloor \frac{n}{T} \rfloor)S(\lfloor \frac{m}{T} \rfloor)$ 设：
$=\sum\limits_{d$=\sum\limits_{T=1}^n S(\lfloor \frac{n}{T} \rfloor)S(\lfloor \frac{m}{T} \rfloor) T^2 F(T)$ 到此，问题解决。但代码运行时间2.23s
（时限2.5s,刚好ac），肯定还有优化，也是
一个有难度且非常重要的优化。观察 研究 ：
当 ，设 ，
当 ，
设 ，
发现 还是积函数，
可以在线性筛中解决。具体代码：
2.3s代码如下
#include<bits/stdc++.h>//1.86s #define LL long long using namespace std; const int N=1e7; const LL mod=20101009; int pr, p[N+10];LL mu[N+10],F[N+10],S[N+10];bool v[N+10]; void init() { memset(v, 0, sizeof(v)); pr=0;mu[0]=0;mu[1]=1; for(int i=2;i<=N;i++) { if(!v[i]) p[++pr]=i,mu[i]=-1; for(int j=1;j<=pr&&p[j]*i<=N;j++) { v[i*p[j]]=true; if(i%p[j]==0) {mu[i*p[j]]=0; break;} mu[i*p[j]]=-mu[i]; } } memset(F,0,sizeof(F)); for(int i=1;i<=N;i++)for(int j=i;j<=N;j+=i) F[j]=(F[j]+mu[j/i]*i%mod+mod)%mod; for(int i=2;i<=N;i++)F[i]=(F[i]*i%mod*i%mod+F[i-1]+mod)%mod; S[1]=1;for(int i=2;i<=N;i++)S[i]=(S[i-1]+i)%mod; } LL calc(LL n,LL m) { LL ans=0; for(LL l=1,r;l<=n;l=r+1) { r=min(n/(n/l),m/(m/l)); ans=(ans+(F[r]-F[l-1]+mod)%mod*S[n/l]%mod*S[m/l]%mod)%mod; } return ans; } int main() { init(); LL n,m;scanf("%lld%lld",&n,&m);if(n>m)swap(n,m); printf("%lld\n",calc(n,m)); return 0; }0.4s代码如下：
#include<bits/stdc++.h>//400ms #define LL long long using namespace std; const int N=1e7; const LL mod=20101009; int pr, p[N+10];LL mu[N+10],F[N+10],S[N+10];bool v[N+10]; void init() { memset(v, 0, sizeof(v));memset(F,0,sizeof(F)); pr=0;mu[0]=0;mu[1]=1,F[1]=1; for(int i=2;i<=N;i++) { if(!v[i]) p[++pr]=i,mu[i]=-1,F[i]=(1*mu[i]+i*mu[1])%mod; for(int j=1;j<=pr&&p[j]*i<=N;j++) { v[i*p[j]]=true; if(i%p[j]==0) {mu[i*p[j]]=0;F[i*p[j]]=F[i]*p[j]%mod; break;} mu[i*p[j]]=-mu[i]; F[i*p[j]]=F[i]*F[p[j]]%mod; } } for(int i=2;i<=N;i++)F[i]=(F[i]*i%mod*i%mod+F[i-1]+mod)%mod; S[1]=1;for(int i=2;i<=N;i++)S[i]=(S[i-1]+i)%mod; } LL calc(LL n,LL m) { LL ans=0; for(LL l=1,r;l<=n;l=r+1) { r=min(n/(n/l),m/(m/l)); ans=(ans+(F[r]-F[l-1]+mod)%mod*S[n/l]%mod*S[m/l]%mod)%mod; } return ans; } int main() { init(); LL n,m;scanf("%lld%lld",&n,&m);if(n>m)swap(n,m); printf("%lld\n",calc(n,m)); return 0; }
- 1