Mobius

发表于 | 更新于 | 评论数： | 阅读次数： | 阅读次数：
本文字数： 2.7k | 阅读时长 ≈ 5 分钟

Mobius

Mobius（莫比乌斯）这东西看得我是真的头痛，网上找了好多博客，只看懂了一点点，完全不会证明，数学太菜了。

推荐一个博客

理论部分

莫比乌斯函数

莫比乌斯函数( $\mu(d)$ )

  1. 当d == 1时， $\mu(d)=1$
  2. 当d == $p_1$*$p_2$*…*$p_k$ 时, $\mu(d)$ = $(-1)^{k}$
  3. 当d 等于其他情况时，$\mu(d)=0$
  4. $\sum_{d|n}{\mu(d)}=$$\begin{cases}1& (n=1) \\ 0 & (n>1)\end{cases}$
  5. $\sum_{d|n}{\frac{\,u(d)}{d}}=\frac{\phi(n)}{n}$

莫比乌斯反演

关于莫比乌斯反演，其实就是求的关于 F(n) 和 f(n) 之间的关系

由于不会证明，只能提供两个公式了（也许哪天我会证了来补一下，溜…）

  1. $F(n)=\sum_{d|n}{f(d)} —> f(n)=\sum_{d|n}{\mu(d)F(\frac{n}{d})}$
  2. $F(n)=\sum_{n|d}{f(d)}—>f(n)=\sum_{n|d}{\mu(\frac{d}{n})F(d)}$

整除分块

整除分块也是一个很重要的东西

引入问题：

  1. $\sum_{i=1}^{n}{\frac{n}{i}}$ 对于这个的求解，如果n很大很明显会超时

求解：我们通过打表可以发现其实有很多重复的，那么我们的关键就是计算重复的部分，这样就分成了很多块，我们发现每一块的最后一个数字是 n/(n/i)

1
2
3
4
5
for(int l=1,r;l<=n;l=r+1)
{
    r=n/(n/l);
    ans+=(r-l+1)*(n/l);
}

当然了，在莫比乌斯函数的应用的时候可能也会遇到整除分块的应用。

板子

莫比乌斯函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N = 1e5 + 5;
int mu[N],prime[N],b[N],tot;
void getMobius(){
    mu[1] = 1; //μ函数的1是特殊情况 
    for(int i = 2; i <= N; ++i){
        if(!b[i]){
            prime[++tot] = i;
            mu[i] = -1; //质数的μ值一定为-1 
        }
        for(int j = 1; j <= tot; ++j){
            if(i * prime[j] > N) break;
            b[i * prime[j]] = 1;
            if(i % prime[j] == 0){
                mu[i * prime[j]] = 0;//i中已经包括了prime[j] 
                break;
            }
            else{
                mu[i * prime[j]] = -mu[i];//不能整除，意味着i中原没有prime[j]这个素因子 
            }
        }
    }
}

题目

hdu 1695

莫比乌斯入门题：

题意要求gcd(x,y)=k的对数，那么我们可以转化一下，变成求gcd(x/k,y/k)==1的对数。

于是就变成了在 [1,b/k] 和 [1,d/k] 之间求 gcd(x,y)==1 的对数（之后的b，d均为除以 k 之后的结果）

再联想到莫比乌斯反演公式的第二条，我们就可以得到两个函数

F(t)=(gcd(x,y)%t==0的对数)

f(t)=(gcd(x,y)==t的对数)

接下去我们要求的就是gcd(x,y)==1的对数，那么就是求f（1），这时候就要继续用莫比乌斯反演公式的第二条，刚刚我们用了前半部分，现在我们用后半部分，可以得到f(1)=mu[1]*F(1)+mu[2]*F(2)+…+mu[min(b,d)]*F(min(b,d))

显然我们可以得到F(t)=(b/t)*(d/t)

但是我们要考虑重复部分，因为在计算的时候是有一部分重复的。

刚才我们得到了f(1)，即区间 [1,b] 和 [1,d] 之间 gcd(x,y)==1 的所有对数，那么重复的部分在哪里呢？当然是区间 [1,min(b,d)] 和 [1,min(b,d)] 之间了，那么答案就出来了，答案为

ans(区间 [1,b] 和 [1,d] ) - ans(区间 [1,min(b,d)] 和 [1,min(b,d)])/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// getMobius() 这个直接使用上面的板子
getMobius();
int t;
cin>>t;
int a,b,c,d,k;
int ca=0;
while(t--){
    ca++;
    cin>>a>>b>>c>>d>>k;
    if(k==0){  //注意0的时候特判一下，不然会re
        cout<<"Case "<<ca<<": ";
        cout<<0<<endl;
        continue;
    }
    b/=k;
    d/=k;
    ll ans1=0,ans2=0;
    for(int i=1;i<=min(b,d);i++){
        ans1+=(ll)mu[i]*(b/i)*(d/i);   //这里注意long long,不然会wa
        ans2+=(ll)mu[i]*(min(b,d)/i)*(min(b,d)/i);
    }
    cout<<"Case "<<ca<<": ";
    cout<<ans1-ans2/2<<endl;
}