1 条题解
-
0
问题
给出 （），求 。
题解
$=\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^n d*\lbrack\gcd(i,j)=d\rbrack$ $=\sum\limits_{d=1}^n \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{n}{d}} 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{n}{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{n}{d}}\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{n}{d}}\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}}\lbrack a|i \rbrack\sum\limits_{j=1}^{\frac{n}{d}}\lbrack a|j \rbrack$ $=\sum\limits_{d=1}^n d \sum\limits_{a=1}^{\frac{n}{d}}\mu(a)\lfloor\frac{n}{ad}\rfloor\lfloor\frac{n}{ad}\rfloor$ 注：到此为止，如果不进一步优化，结果50分超时。 设 $=\sum\limits_{d=1}^n d \sum\limits_{\frac{T}{d}=1}^{\frac{n}{d}}\mu(\frac{T}{d})\lfloor \frac{n}{T} \rfloor\lfloor \frac{n}{T} \rfloor$ $=\sum\limits_{d=1}^nd\sum\limits_{T=1}^n\mu(\frac{T}{d})\lfloor \frac{n}{T} \rfloor \lfloor \frac{n}{T} \rfloor$ $=\sum\limits_{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{n}{T} \rfloor \sum\limits_{d|T}d* \mu(\frac{T}{d})$ 设： ，可以前缀和。
初始化代码如下：
F[0]=0;for(int i=1;i<=N;i++)
for(int j=i;j<=N;j+=i)
F[j]+=mu[j/i]*i;$=\sum\limits_{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{n}{T} \rfloor F(T)$ 具体代码如下：
50分超时代码：
#include<bits/stdc++.h> #define LL long long using namespace std; const int N=2e6; int pr, p[N+10];LL mu[N+10];bool v[N+10]; void init() { memset(v, 0, sizeof(v)); pr=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]; } //mu[i]+=mu[i-1]; } for(int i=2;i<=N;i++)mu[i]+=mu[i-1]; } LL calc(LL n) { LL ans=0; for(LL i=1;i<=n;i++) { LL sum=0; for(LL l=1, r, m=n/i;l<=m;l=r+1) { r=m/(m/l); sum+=(mu[r]-mu[l-1])*(m/l)*(m/l); } ans+=sum*i; } return ans; } int main() { init(); int T;scanf("%d",&T); while(T--) { LL n;scanf("%lld",&n); printf("%lld\n",calc(n)); } return 0; }100分代码：
#include<bits/stdc++.h> #define LL long long using namespace std; const int N=2e6; int pr, p[N+10];LL mu[N+10],F[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]; } } F[0]=0; for(int i=1;i<=N;i++)for(int j=i;j<=N;j+=i) F[j]+=mu[j/i]*i; for(int i=1;i<=N;i++)F[i]+=F[i-1]; } LL calc(LL n) { LL ans=0; for(LL l=1, r;l<=n;l=r+1) { r=n/(n/l); ans+=(F[r]-F[l-1])*(n/l)*(n/l); } return ans; } int main() { init(); int T;scanf("%d",&T); while(T--) { LL n;scanf("%lld",&n); printf("%lld\n",calc(n)); } return 0; }
- 1