[bzoj2154]Crash的数字表格(mobius反演)

题意：$\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {lcm(i,j)} } $

解题关键：

$\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {lcm(i,j)} } = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {\frac{{i*j}}{{\gcd (i,j)}}} } $

枚举gcd，上式化为：

$\sum\limits_{d = 1}^{\min (n,m)} {d\sum\limits_{\begin{array}{*{20}{c}}
{\gcd (i,j) = = 1}\\
{1 < = i < = n/d}\\
{1 < = j < = m/d}
\end{array}} {i*j} } $

令

$f(n,m,k) = \sum\limits_{\begin{array}{*{20}{c}}
{\gcd (i,j) = = k}\\
{1 < = i < = n}\\
{1 < = j < = m}
\end{array}} {i*j} $

由于

$sum(n,m) = \sum\limits_{\begin{array}{*{20}{c}}
{1 < = i < = n}\\
{1 < = j < = m}
\end{array}} {i*j} = \frac{{n(n + 1)}}{2}\frac{{m(m + 1)}}{2}$

$\begin{array}{l}
F(n,m,k) = \sum\limits_{k|d} {f(n,m,d) = \sum\limits_{\begin{array}{*{20}{c}}
{1 < = i < = n}\\
{1 < = j < = m}\\
{k|\gcd (i,j)}
\end{array}} {i*j} = {k^2}sum(\left\lfloor {\frac{n}{k}} \right\rfloor ,\left\lfloor {\frac{m}{k}} \right\rfloor )} \\
f(n,m,k) = \sum\limits_{k|d} {u(\frac{d}{k})F(n,m,d)}
\end{array}$

而此题中，$k==1$,

则，

$\begin{array}{l}
f(n,m,1) = \sum\limits_{d = 1}^{\min (n,m)} {u(d)F(n,m,d)} \\
= \sum\limits_{d = 1}^{\min (n,m)} {u(d){d^2}sum(\left\lfloor {\frac{n}{d}} \right\rfloor ,\left\lfloor {\frac{m}{d}} \right\rfloor )} \\
ans = \sum\limits_{d = 1}^{\min (n,m)} {d*f(\left\lfloor {\frac{n}{d}} \right\rfloor ,\left\lfloor {\frac{m}{d}} \right\rfloor ,1)}
\end{array}$

求解ans和$f$函数复杂度都是$O(\sqrt n )$，所以最终复杂度为$O(n)$。

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<iostream>

 #define Sum(x,y) (x*(x+1)/2%mod*(y*(y+1)/2%mod)%mod)

 using namespace std;

 typedef long long ll;

 const ll mod=;

 const ll maxn=+;

 ll n,m;

 bool vis[maxn];

 ll prime[maxn],mu[maxn],sum1[maxn];

 void init_mu(ll n){

     ll cnt=;

     mu[]=;

     for(ll i=;i<n;i++){

         if(!vis[i]){

             prime[cnt++]=i;

             mu[i]=-;

         }

         for(ll j=;j<cnt&&i*prime[j]<n;j++){

             vis[i*prime[j]]=;

             if(i%prime[j]==){mu[i*prime[j]]=;break;}

             else { mu[i*prime[j]]=-mu[i];}

         }

     }

     sum1[]=;

     for(ll i=;i<n;i++) sum1[i]=(sum1[i-]+1ll*mu[i]*i*i)%mod;

 }

 ll calf(ll n,ll m){

     ll ans=,pos,len=min(n,m);

     for(ll i=;i<=len;i=pos+){

         pos=min(n/(n/i),m/(m/i));

         //ans+=(sum1[pos]-sum1[i-1])%mod*((n/i)*((n/i)+1)/2%mod*(((m/i)+1)*(m/i)/2%mod)%mod);

         ans+=(sum1[pos]-sum1[i-])%mod*Sum(n/i,m/i)%mod;//最好用函数写出

         ans%=mod;

     }

     return ans;

 }

 ll calres(ll n,ll m){

     ll ans=,pos,len=min(n,m);

     for(ll i=;i<=len;i=pos+){

         pos=min(n/(n/i),m/(m/i));

         ans+=(i+pos)*(pos-i+)/%mod*calf(n/i,m/i)%mod;

         ans%=mod;

     }

     return (ans%mod+mod)%mod;

 }

 int main(){

     scanf("%lld%lld",&n,&m);

     init_mu(min(n,m)+);

     printf("%lld\n",calres(n,m));

     return ;

 }

巴特西

[bzoj2154]Crash的数字表格(mobius反演)

最新文章

热门文章