精华内容
下载资源
问答
  • 莫比乌斯函数

    千次阅读 2017-07-28 13:32:50
    莫比乌斯函数

    对于莫比乌斯函数,首先我们要知道它的符号是什么?

     

    它定义为:

    (1)若d=1,那么μ(d)=1

    (2)若d=p1*p2*````pk(pi均为互异素数),那么μ(d)=(-1)^k

    (3)其他情况μ(d)=0

    莫比乌斯函数的性质:

    (1)对于任意正整数n有


    (2)对于任意正整数n有


    莫比乌斯函数求解代码:

    #include<stdio.h>
    #include<iostream>
    using namespace std;
    typedef long long ll;
    ll mu[100005];
    void mobius(ll mn)  
    {  
        mu[1]=1;  
        for(ll i=1;i<=mn;i++){  
            for(ll j=i+i;j<=mn;j+=i){  
                mu[j]-=mu[i];  
            }  
        }  
    }
    int main()
    {
    	mobius(100000);
    }


    展开全文
  • 莫比乌斯函数总结性质:\(\sum_{d|n}\mu(d)=[n==1]\)这个可以用组合数的性质来证,形象点的话就是杨辉三角。因为恒等式:\(\sum_{i=0}^{n}(-1)^nC_{n}^{i}=0\).莫比乌斯反演:形式一:已知:\(g(n)=\sum_{d|n}f(d)\)...

    莫比乌斯函数总结

    性质:\(\sum_{d|n}\mu(d)=[n==1]\)

    这个可以用组合数的性质来证,形象点的话就是杨辉三角。

    因为恒等式:\(\sum_{i=0}^{n}(-1)^nC_{n}^{i}=0\).

    莫比乌斯反演:

    形式一:

    已知:\(g(n)=\sum_{d|n}f(d)\),则有:\(f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})\).

    证明如下:

    \[\sum_{d|n}\mu(d)g(\frac{n}{d})=\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}f(k)

    \]

    交换求和次序,有:

    \[\begin{aligned}

    &\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}f(k)\\

    =&\sum_{k|n}f(k)\sum_{d|\frac{n}{k}}\mu(d)\\

    =&\sum_{k|n}f(k)[\frac{n}{k}=1]=f(n)

    \end{aligned}

    \]

    故得证.

    形式二:

    已知:\(g(n)=\sum_{n|d}f(d)\),则有:\(f(n)=\sum_{n|d}\mu(\frac{d}{n})g(d)\).

    证明如下:

    令\(k=\frac{d}{n}\),则有:

    \[\begin{aligned}

    &\sum_{n|d}\mu(\frac{d}{n})g(d)\\

    =&\sum_{k=1}^{\infty}\mu(k)g(nk)\\

    =&\sum_{k=1}^{\infty}\mu(k)\sum_{nk|t}f(t)

    \end{aligned}

    \]

    交换求和次序,有:

    \[\begin{aligned}

    &\sum_{k=1}^{\infty}\mu(k)\sum_{nk|t}f(t)\\

    =&\sum_{n|t}f(t)\sum_{k|\frac{t}{n}}\mu(k)\\

    =&\sum_{n|t}f(t)[\frac{t}{n}=1]=f(n)

    \end{aligned}

    \]

    故得证.

    常用技巧(应用):

    一个性质:

    \[\lfloor\frac{\lfloor\frac{x}{a}\rfloor}{b}\rfloor=\lfloor\frac{x}{ab}\rfloor

    \]

    证明如下:

    令\(y=\lfloor\frac{x}{a}\rfloor,z=\lfloor\frac{x}{ab}\rfloor\),显然有:\(x=zab+c,c\leq ab\).

    等式两边同时除以\(a\)并向下取整有:\(y=zb+\lfloor\frac{c}{a}\rfloor\).

    再同时除以\(b\)并向下取整:\(\lfloor\frac{\lfloor\frac{x}{a}\rfloor}{b}\rfloor=z+\lfloor\frac{\lfloor\frac{c}{a}\rfloor}{b}\rfloor\).

    之后就比较显然了。

    整除分块:

    整除分块经常在相关数论问题中用到,主要是用来解决下列求和式:

    \[\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor

    \]

    证明我就不写了,就说点有用的性质吧:

    对于\(1\leq i\leq n\),\(\lfloor\frac{n}{i}\rfloor\)只有至多\(2\sqrt{n}\)个不同取值。

    对于任一\(x\),当\(x\leq i\leq \lfloor\frac{n}{\lfloor\frac{n}{x}\rfloor}\rfloor\)时,\(\lfloor\frac{n}{i}\rfloor\)的值都相等。

    有了上面两个性质,那么可以加速求和式,复杂度为\(\sqrt{n}\)。

    例一:

    求:\(\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]\).

    \[\begin{aligned}

    &\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]\\

    =&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d)\\

    =&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i,d|j}\mu(d)

    \end{aligned}

    \]

    说明一下:从第一步到第二步多出来一个和式,就相当于一个容斥的过程,考虑所有的\((i,j)\),对于他们的\(gcd\)来进行容斥:先加上所有的情况,然后减去\(gcd\)为\(2,3,5...\)倍数的情况,但会多减,所以加回来。

    之后再进行变换得:

    \[\begin{aligned}

    &\sum_{d}\mu(d)\sum_{i=1}^{n}\sum_{d|i}\sum_{j=1}^{m}\sum_{d|j}\\

    =&\sum_{d}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor

    \end{aligned}

    \]

    后面的部分直接整除分块,然后预处理\(\mu\)的前缀和就行了。

    例二:

    求:\(\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)\)

    这个和第一个比较类似,我们变化一下就有:

    \[\begin{aligned}

    &\sum{d}\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d]\\

    =&\sum{d}\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i,j)=1]

    \end{aligned}

    \]

    根据例一得:

    \[\begin{aligned}

    &\sum{d}\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i,j)=1]\\

    =&\sum{d}\sum_t\mu(t)\lfloor\frac{n}{dt}\rfloor\lfloor\frac{m}{dt}\rfloor

    \end{aligned}

    \]

    令\(T=dt\),则上式可化为:

    \[\begin{aligned}

    =&\sum{\frac{T}{t}}\sum_{t}\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\\

    =&\sum_{T}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{t|T}\mu(t)\frac{T}{t}\\

    =&\sum_T\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\varphi(T)

    \end{aligned}

    \]

    说说为什么最后转化为了欧拉函数:

    欧拉函数有个十分有用的性质:\(\sum_{d|n}\varphi(d)=n\),证明的话主要从\(f(n)=\sum_{d|n}\varphi(d)\)这个函数为积性函数入手。同时还有两个个性质也比较有用:一个是\(\varphi(p^m)=p^m-p^{m-1}\),另一个是小于\(n\)的数中,与\(n\)互质的数的和为\(\frac{n\varphi(n)}{2},n>1\),为什么呢?因为有\(gcd(m,n)=gcd(n,n-m),所以是成对的~\)。

    回到正题,有了这个式子反演一下就有:

    \[\varphi(n)=\sum_{d|n}\mu(d)\frac{n}{d}

    \]

    对于例二,整除分块+预处理欧拉函数就行了。

    题意:

    求\(\sum_{i=1}^n\sum_{j=1}^m lcm(i,j)\)。

    思路:

    推导过程如下:

    \[\begin{aligned}

    &\sum_{i=1}^n \sum_{j=1}^m lcm(i,j)\\

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

    =&\sum_d\sum_i\sum_j\frac{ij}{d}(gcd(i,j)=d)\\

    =&\sum_d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ijd(gcd(i,j)=1)\\

    =&\sum_dd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij(gcd(i,j)=1)

    \end{aligned}

    \]

    后面部分是不是很熟悉,我们先求\(sum(n,m)=\sum_i\sum_jij(gcd(i,j)=1)\).

    按照套路,有:

    \[\begin{aligned}

    sum(n,m)=&\sum_i\sum_jij\sum_{d|gcd(i,j)}\mu(d)\\

    =&\sum_d d^2\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij

    \end{aligned}

    \]

    后面部分为两个等差数列求和,显然可以直接数论分块来搞。

    回到原式:

    \[\sum_d d\cdot sum(\lfloor\frac{n}{d}, \frac{m}{d}\rfloor)

    \]

    发现这后面也可以数论分块搞,所以就是分块套分块,总复杂度为\(O(n)\)。

    Code

    #include

    using namespace std;

    typedef long long ll;

    const int N = 1e7 + 5, MOD = 20101009;

    int n, m;

    int mu[N], p[N], sum[N];

    bool chk[N];

    void init() {

    mu[1] = 1;

    int cnt = 0, k = min(n, m);

    for(int i = 2; i <= k; i++) {

    if(!chk[i]) p[++cnt] = i, mu[i] = -1;

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

    chk[i * p[j]] = 1;

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

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

    }

    }

    for(int i = 1; i <= k; i++) sum[i] = ((sum[i - 1] + 1ll * mu[i] * i * i % MOD) % MOD + MOD) % MOD;

    }

    int Sum(int x) {

    return 1ll * x * (x + 1) / 2 % MOD;

    }

    int calc(int n, int m) {

    int ans = 0;

    for(int i = 1, j; i <= min(n, m); i = j + 1) {

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

    ans = (ans + 1ll * (sum[j] - sum[i - 1] + MOD) * Sum(n / i) % MOD * Sum(m / i) % MOD) % MOD;

    }

    return ans;

    }

    int solve(int n, int m) {

    int ans = 0;

    for(int i = 1, j; i <= min(n, m); i = j + 1) {

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

    ans = (ans + 1ll * (i + j) * (j - i + 1) / 2 % MOD * calc(n / i, m / i) % MOD) % MOD;

    }

    return ans;

    }

    int main() {

    #ifdef heyuhhh

    freopen("input.in", "r", stdin);

    #else

    ios::sync_with_stdio(false); cin.tie(0);

    #endif

    cin >> n >> m;

    init();

    cout << solve(n, m);

    return 0;

    }

    展开全文
  • 1240 莫比乌斯函数 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 莫比乌斯函数,由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)(miu(n))作为莫比乌斯函数的记号。...

    1240 莫比乌斯函数

    基准时间限制:1 秒
    空间限制:131072 KB
    分值: 0
    难度:基础题

    莫比乌斯函数,由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)(miu(n))作为莫比乌斯函数的记号。(据说,高斯(Gauss)比莫比乌斯早三十年就曾考虑过这个函数)。

    具体定义如下:
    如果一个数包含平方因子,那么miu(n)=0。例如:miu(4),miu(12),miu(18)=0
    如果一个数不包含平方因子,并且有k个不同的质因子,那么miu(n)=(1)k
    例如:miu(2),miu(3),miu(30)=1,miu(1),miu(6),miu(10)=1
    给出一个数n, 计算miu(n)

    Input
    输入包括一个数n,(2<=n<=109)

    Output
    输出miu(n)。

    Input示例
    5
    Output示例
    -1


    根据定义直接写

    #include<bits/stdc++.h>
    using namespace std;
    int miu(int n){
        int cnt=0;
        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                n/=i;
                cnt++;
                if(n%i==0)
                    return 0;
            }
        }
        if(n!=1)    cnt++;
        return cnt&1?-1:1;
    }
    
    int main(){
        int n;
        scanf("%d",&n);
        printf("%d\n",miu(n));
        return 0;
    }
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,651
精华内容 1,060
关键字:

莫比乌斯函数