BZOJ 2154/2693 Crash的数字表格/jzptab (莫比乌斯反演)

题目大意：求$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$的和

易得$\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{gcd(i,j)}$

套路1：提取出$gcd$

$\sum_{k=1}^{n}\frac{1}{k}\sum_{i=1}^{n}\sum_{j=1}^{m}ij$

$\sum_{k=1}^{n}k\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor}ij$

$\sum_{k=1}^{n}k\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor}\sum_{d|gcd(i,j)}\mu(d)$

套路2：继续提取$gcd$

$\sum_{k=1}^{n}k\sum_{d=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor}[gcd(i,j)==d]ij$

$\sum_{k=1}^{n}k\sum_{d=1}^{\left \lfloor \frac{n}{k} \right \rfloor}d^{2}\sum_{i=1}^{\left \lfloor \frac{n}{kd} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{kd} \right \rfloor}ij$

$\sum_{i=1}^{\left \lfloor \frac{n}{kd} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{kd} \right \rfloor}ij$可以$O(1)$计算出来

套路3：令$Q=kd$

$\sum_{Q=1}^{n}\sum_{i=1}^{\left \lfloor \frac{n}{Q} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{Q} \right \rfloor}ij\sum_{d|Q}\frac{Q}{d}(d)^{2}\mu(d)$

$\sum_{d|Q}\frac{Q}{d}(d)^{2}\mu(d)$显然是积性函数

然后问题就解决了

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N 10010000

 #define maxn 10000000

 #define ll long long

 #define uint unsigned int

 #define rint register int

 using namespace std;

 int n,m,T,cnt;

 int mu[N],pr[N],use[N];

 int f[N],F[N];

 const int mod=;

 void Pre()

 {

     mu[]=;f[]=;

     for(int i=;i<=maxn;i++)

     {

         if(!use[i]) pr[++cnt]=i,mu[i]=-,f[i]=(1ll*i*(-i))%mod;

         for(rint j=;j<=cnt&&i*pr[j]<=maxn;j++){

             use[i*pr[j]]=;

             if(i%pr[j]){

                 mu[i*pr[j]]=-mu[i];

                 f[i*pr[j]]=1ll*f[i]*f[pr[j]]%mod;

             }else{

                 mu[i*pr[j]]=;

                 f[i*pr[j]]=1ll*f[i]*pr[j]%mod;

                 break;

             }

         }

     }

     for(int i=;i-<=maxn;i+=)

     {

         F[i+]=(1ll*F[i-]+f[i+])%mod;

         F[i+]=(1ll*F[i+]+f[i+])%mod;

         F[i+]=(1ll*F[i+]+f[i+])%mod;

         F[i+]=(1ll*F[i+]+f[i+])%mod;

     }

 }

 ll solve(int n,int m)

 {

     ll ans=,sn,sm;

     if(n>m) swap(n,m);

     for(int i=,la;i<=n;i=la+)

     {

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

         sn=(1ll*(n/i)*(n/i+)/)%mod;

         sm=(1ll*(m/i)*(m/i+)/)%mod;

         (ans+=1ll*sn*sm%mod*(F[la]-F[i-]))%=mod;

     }ans=(ans%mod+mod)%mod;

     return ans;

 }

 int main()

 {

     //freopen("t1.in","r",stdin);

     scanf("%d",&T);

     Pre();

     int n,m;

     while(T--)

     {

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

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

     }

     return ;

 }

调试部分的代码..留个纪念吧

 int ps[N],son[N],d[N],num,nson;

 void dfs_son(int s,int dep)

 {

     if(dep>num) {son[++nson]=s;return;}

     for(int j=;j<=d[dep];j++)

         dfs_son(s,dep+),s*=ps[dep];

 }

 ll g[N];

 void check()

 {

     for(int i=;i<=maxn;i++){

         int sq=sqrt(i),x=i;

         num=nson=;

         for(int j=;j<=cnt&&pr[j]<=sq;j++)

             if(x%pr[j]==){

                 ps[++num]=pr[j];

                 while(x%pr[j]==) d[num]++,x/=pr[j];

             }

         if(x!=) ps[++num]=x,d[num]=;

         dfs_son(,);

         for(int j=;j<=nson;j++)

             (g[i]+=mu[son[j]]*son[j]%mod)%=mod,

             son[j]=;

         g[i]=g[i]*i%mod;

         for(int i=;i<=num;i++)

             d[i]=;

     }

 }

巴特西

BZOJ 2154/2693 Crash的数字表格/jzptab (莫比乌斯反演)

最新文章

热门文章