莫比乌斯函数 && HDU-1695

莫比乌斯函数定义：

$$\mu(d)=\begin{cases}
1 &\text{d = 1}\\
(-1)^r &\text{$d=p_1p_2...p_r,其中p_i为不同的素数$}\\
0 &\text{else}
\end{cases}$$

性质：

(1)$\sum_{d|n}\mu(d)=[n=1]$

(2)$\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}$

莫比乌斯反演（没写定义域之类的）：

$F(n)=\sum_{d|n}f(d)或F(n)=\sum_{d|n}f(\frac{n}{d}){\quad}{\Leftrightarrow}{\quad}f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})或f(n)=\sum_{d|n}\mu(\frac{n}{d})F(d)$

$F(n)=\sum_{n|d}f(d){\quad}{\Leftrightarrow}{\quad}f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)$（一般用的都是这种）
并不清楚为什么d没有上限

证明：https://wenku.baidu.com/view/fbec9c63ba1aa8114431d9ac.html

（性质1根据二项式定理直接证，那么反演公式可以根据性质1证（第二种反演的证法类似第一种反演，式子可以做类似的变换））

线性筛莫比乌斯函数

设mu[i]为i的莫比乌斯函数值

首先，mu[1]=1

mu[一个质数]=-1

对于一个合数x，设其最小质因子为p，那么它会被q=x/p筛掉，在它被q筛掉时，判断一下q%p是否为0，如果为0则说明q有至少1个质因子p，因此x有至少2个质因子p，那么mu[x]=0；否则mu[x]=-mu[q]

模板题：给定i,j,k，求$\sum_{i=1}^n{\sum_{j=1}^m{[(i,j)=k]}}$

设$f(x)=\sum_{i=1}^n{\sum_{j=1}^m{[(i,j)=x]}}$

设$F(x)=\sum_{x|d}{\sum_{i=1}^n{\sum_{j=1}^m{[(i,j)=d]}}}=\sum_{i=1}^n{\sum_{j=1}^m{[x|(i,j)]}}$

显然$F(x)={\lfloor}{\frac{n}{x}}{\rfloor}*{\lfloor}{\frac{m}{x}}{\rfloor}$

那么可以根据F(x)计算f(x)得到答案

（从中看出一类通用的关系："满足f(a)是x的倍数/因数的a个数""满足f(a)等于x的a的个数"间的转换）

https://vjudge.net/problem/HDU-1695

（此题跟以上"模板题"题面类似，但不完全一样，要加一些特判）

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 #define N 100100

 ll prime[N+],len,mu[N+];

 bool nprime[N+];

 ll a,c,n,m,k,ans,a2;

 ll F(ll x)    {return (m/x)*(n/x);}

 ll F2(ll x)    {return (n/x)*(n/x);}

 int main()

 {

     ll i,j,T,TT;

     mu[]=;

     for(i=;i<=N;i++)

     {

         if(!nprime[i])    prime[++len]=i,mu[i]=-;

         for(j=;j<=len&&i*prime[j]<=N;j++)

         {

             nprime[i*prime[j]]=;

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

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

         }

     }

     scanf("%lld",&T);

     for(TT=;TT<=T;TT++)

     {

         scanf("%lld%lld%lld%lld%lld",&a,&n,&c,&m,&k);

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

         ans=a2=;

         if(k>n||k==)    goto xxx;

         for(i=;i<=n/k;i++)

             ans+=mu[i]*F(i*k);

         for(i=;i<=n/k;i++)

             a2+=mu[i]*F2(i*k);

         ans-=(a2-)/;

         xxx:;

         printf("Case %lld: %lld\n",TT,ans);

     }

     return ;

 }

另外：此题也可以不用莫比乌斯函数做，可以直接容斥

简单来讲就是先算出数组F，其中F[i]=F(i)

然后预处理出n个vector(d1,d2,..,dn)，第i个表示i的所有因子（用枚举每个数的倍数的方式，而不是枚举因子）

然后从大到小枚举i，对于i除自身外所有的因子j，F[j]-=F[i]

对此题并没有什么特别的好处。。只是记一下有这种方法

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 #define N 100100

 ll an[N+];

 ll a,c,n,m,k,ans,a2;

 ll F(ll x)    {return (m/x)*(n/x);}

 ll F2(ll x)    {return (n/x)*(n/x);}

 vector<ll> d[];

 int main()

 {

     ll i,j,T,TT;

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

         for(j=*i;j<=;j+=i)

             d[j].pb(i);

     scanf("%lld",&T);

     for(TT=;TT<=T;TT++)

     {

         scanf("%lld%lld%lld%lld%lld",&a,&n,&c,&m,&k);

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

         ans=a2=;

         if(k>n||k==)    goto xxx;

         for(i=;i<=n;i++)    an[i]=F(i);

         for(i=n;i>=;i--)

             for(j=;j<d[i].size();j++)

                 an[d[i][j]]-=an[i];

         ans+=an[k];

         for(i=;i<=n;i++)    an[i]=F2(i);

         for(i=n;i>=;i--)

             for(j=;j<d[i].size();j++)

                 an[d[i][j]]-=an[i];

         a2+=an[k];

         ans-=(a2-)/;

         xxx:;

         printf("Case %lld: %lld\n",TT,ans);

     }

     return ;

 }

资料待看：

https://www.cnblogs.com/chenyang920/p/4811995.html

https://blog.csdn.net/danliwoo/article/details/51866867

巴特西

莫比乌斯函数 && HDU-1695

最新文章

热门文章