1 条题解
-
0
问题
给出 ，求 。
题解
设 $=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \frac{i*j}{\gcd(i,j)}$ $=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \sum\limits_{d=1}^n\frac{i*j}{d}\lbrack\gcd(i,j)=d\rbrack$ $=\sum\limits_{d=1}^n \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}} \frac{id*jd}{d}\lbrack\gcd(i,j)=1\rbrack$ $=\sum\limits_{d=1}^n d \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}} i*j\lbrack\gcd(i,j)=1\rbrack$ $=\sum\limits_{d=1}^n d \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}i*j\sum\limits_{a | \gcd(i,j)}\mu(a)$ $=\sum\limits_{d=1}^n d \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 \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 \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 \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 \sum\limits_{\frac{T}{d}=1}^{\frac{n}{d}}T\frac{T}{d}\mu(\frac{T}{d})S(\lfloor \frac{n}{T} \rfloor)S(\lfloor \frac{m}{T} \rfloor)$ $=\sum\limits_{d=1}^n\sum\limits_{T=1}^n\frac{T}{d}\mu(\frac{T}{d})TS(\lfloor \frac{n}{T} \rfloor)S(\lfloor \frac{m}{T} \rfloor)$ $=\sum\limits_{T=1}^n TS(\lfloor \frac{n}{T} \rfloor)S(\lfloor \frac{m}{T} \rfloor)\sum\limits_{d=1}^n\frac{T}{d}\mu(\frac{T}{d})$ 设： $F(T)=\sum\limits_{d=1}^n\frac{T}{d}* \mu(\frac{T}{d})$
$=\sum\limits_{d$=\sum\limits_{T=1}^n S(\lfloor \frac{n}{T} \rfloor)S(\lfloor \frac{m}{T} \rfloor)TF(T)$ 到此，问题解决。 但代码运行时间1.86s
（时限2s,刚好ac）， 肯定还有优化，
也是一个有难度且非常重要的优化。观察 研究 ：
1、当 ，
设 ，
2、当 ，
设 ，
发现 还是积函数，
可以在线性筛中解决。具体代码：
1.86s代码如下
#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[i]*i%mod+mod)%mod; for(int i=2;i<=N;i++)F[i]=(F[i]*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)%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]; 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+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
