Mobius反演定理-BZOJ2154

This article is made by Jason-Cow.
Welcome to reprint.
But please post the article's address.

莫比乌斯定理（未完待续......）：

形式1：

形式2：

引理:

证明1：

      右边=带入左边等式，得              

　　　           

　　　　　　

　　　　　　

　　　　　　    又当且仅当 : ，即时，上式非

 　　　　　  

   所以，成立。

 bzoj2154

时间复杂度

 换元：令

/*

*/

此题的精髓就一个字，模

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <map>

 #include <set>

 using namespace std;

 #define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)

 const int mod=,maxn=1e7+;

 int f[maxn],p[maxn],flag[maxn],cnt,S[maxn];

 void init(int n,int m){

   f[]=;

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

     if(!flag[i])p[++cnt]=i,f[i]=(-i)%mod;

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

       flag[i*p[j]]=;

       if(i%p[j]==){f[i*p[j]]=f[i]%mod;break;}

       f[i*p[j]]=((long long)(f[i]%mod)*(f[p[j]]%mod))%mod;

     }

   }

   for(int i=;i<=m;i++)S[i]=((S[i]%mod)+((S[i-]+i)%mod))%mod;

 }

 int main(){

   int n,m;scanf("%d%d",&n,&m);if(n>m)swap(n,m);

   init(n,m);

   int ans=;

   for(int Q=;Q<=n;Q++)

     ans=(ans+(((Q%mod)*(long long)f[Q]*(((long long)S[n/Q]*S[m/Q])%mod))%mod)%mod)%mod;

   printf("%d\n",(ans+mod)%mod);

   return ;

 }

f(n)=∑d|nμ(d)F(nd)=∑d|nμ(d)∑k|ndf(k)=∑k|nf(k)∑d|nkμ(d)