[坑]狄利克雷卷积和反演

danihao123 posted @ 2017年9月25日 12:56 in 大坑 with tags 数论 数学 bzoj 莫比乌斯反演 狄利克雷卷积 , 1218 阅读
转载请注明出处:http://danihao123.is-programmer.com/

开个坑,记录一些和反演以及狄利克雷卷积的东西。

首先积性函数、狄利克雷卷积等基本概念不写了,就讲讲性质吧。

有几个一定要记住的东西:

\[\mu \ast 1 = e\]

\[\varphi \ast 1 = id\]

\[\mu \ast id = \varphi\]

这几个在推式子的过程中都有很大的作用,务必要记住。

所谓莫比乌斯反演,其实就是:

\[F = f \ast 1\Leftrightarrow f = F \ast \mu\]

(谜之音:其实很多所谓“反演题”都没用到这俩性质啊……)

关于莫比乌斯函数本身,还有一个好康的性质:

\[(\mu\ast 1)(k) = \sum_{i = 0}^k (-1)^i C_k^i\]

[BZOJ 2301]Problem b

嗯……经典老题。

推导过程如下(很重要):

\[
\begin{aligned}
\sum_{i = 1}^n \sum_{j = 1}^m [gcd(i, j) = k]
&= \sum_{i = 1}^{\lfloor \tfrac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \tfrac{m}{k} \rfloor} [gcd(i, j) = 1] \\
&= \sum_{i = 1}^{\lfloor \tfrac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \tfrac{m}{k} \rfloor} \sum_{d\mid i, d\mid j} \mu (d) \\
&= \sum_{d = 1}^{min(\lfloor \tfrac{n}{k} \rfloor, \lfloor \tfrac{m}{k} \rfloor)} \mu (d)
\sum_{i = 1}^{\lfloor \tfrac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \tfrac{m}{k} \rfloor} [d\mid i, d\mid j] \\
&= \sum_{d = 1}^{min(\lfloor \tfrac{n}{k} \rfloor, \lfloor \tfrac{m}{k} \rfloor)} \mu (d)\lfloor\tfrac{n}{kd}\rfloor\lfloor\tfrac{m}{kd}\rfloor
\end{aligned}
\]

然后显然\(\lfloor\tfrac{n}{kd}\rfloor\lfloor\tfrac{m}{kd}\rfloor\)这个东西的取值是\(O(\sqrt{n})\)级别的,所以预处理欧拉筛然后搞出来\(\mu\)的前缀和,一次查询\(O(\sqrt{n})\)搞即可……

/**************************************************************
    Problem: 2301
    User: danihao123
    Language: C++
    Result: Accepted
    Time:10348 ms
    Memory:1456 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using std::swap; using std::min;
const int maxn = 50005;
bool vis[maxn];
int prime[maxn];
int prime_tot = 0;
int miu[maxn];
int S[maxn];
int N = 50000;
void shai() {
    miu[1] = 1;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) {
            miu[i] = -1;
            prime[++prime_tot] = i;
        }
        for(int j = 1; j <= prime_tot && i * prime[j] <= N; j++) {
            int m = i * prime[j];
            vis[m] = true;
            if(i % prime[j] == 0) {
                miu[m] = 0;
                break;
            } else {
                miu[m] = -miu[i];
            }
        }
    }
    S[0] = 0;
    for(int i = 1; i <= N; i++) {
        S[i] = S[i - 1] + miu[i];
    }
}
int sum(int i, int j) {
    return S[j] - S[i - 1];
}
 
int calc(int a, int b) {
    if(a > b) {
        swap(a, b);
    }
    int ans = 0;
    for(int i = 1, last = 0; i <= a; i = last + 1) {
        last = min(a / (a / i), b / (b / i));
        ans += sum(i, last) * (a / i) * (b / i);
    }
    return ans;
}
 
int main() {
    shai();
    int m;
    scanf("%d", &m);
    while(m--) {
        int a, b, c, d, k;
        scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
        int ans = 0;
        ans += calc(b / k, d / k);
        ans -= calc((a-1) / k, d / k);
        ans -= calc(b / k, (c-1) / k);
        ans += calc((a-1) / k, (c-1) / k);
        printf("%d\n", ans);
    }
    return 0;
}

[BZOJ 2820]YY的GCD

劲啊……

用\(p(x)\)来表示\(x\)是否为素数(是的话返回1,否则返回0)。

然后大概就这样子:

\[
\begin{align*}
\sum_{i = 1}^n \sum_{j = 1}^m p(gcd(i, j))
& = \sum_{k = 1}^{min(n, m)} p(k)
\sum_{d = 1}^{min(\lfloor \tfrac{n}{k} \rfloor, \lfloor \tfrac{m}{k} \rfloor)} \mu (d)\lfloor\tfrac{n}{kd}\rfloor\lfloor\tfrac{m}{kd}\rfloor
\end{align*}
\]

然后那个\(kd\)太不顺眼了,我们就直接枚举她吧!(逃

然后式子就变成了这样:

\[\sum_{T = 1}^{min(n, m)} \lfloor\tfrac{n}{T}\rfloor\lfloor\tfrac{m}{T}\rfloor\sum_{d\mid T} p(d)\mu(\tfrac{T}{d})\]

然后你发现了啥?中间那个\(\sum_{d\mid T} p(d)\mu(\tfrac{T}{d})\)不就是\((p\ast\mu)(T)\)吗?于是乎问题的瓶颈变成了高效的预处理\(p\ast\mu\)。

不幸的事情是这个函数不是积性函数,但是线性筛还是可以做的吖!

/**************************************************************
    Problem: 2820
    User: danihao123
    Language: C++
    Result: Accepted
    Time:6056 ms
    Memory:430508 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cstdlib>
using namespace std;
const int maxn = 10000000;
typedef long long ll;
ll miu[maxn + 1];
ll vis[maxn + 1];
ll f[maxn + 1];
int low[maxn + 1], lowp[maxn + 1];
inline void sieve() {
    static int prm[maxn + 1];
    int cnt = 0;
    miu[1] = 1; vis[1] = 1; f[1] = 0;
    for(int i = 2; i <= maxn; i ++) {
        if(!vis[i]) {
            prm[cnt ++] = i;
            miu[i] = -1;
            f[i] = 1;
            low[i] = i;
            lowp[i] = 1;
        }
        for(int j = 0; j < cnt; j ++) {
            int p = prm[j];
            int v = p * i;
            if(v > maxn) break;
            vis[v] = 1;
            if(i % p == 0) {
                miu[v] = 0;
                f[v] = miu[v / p];
                break;
            } else {
                miu[v] = miu[i] * miu[p];
                f[v] = f[i] * miu[p] + miu[i];
                low[v] = p; lowp[i] = 1;
            }
        }
    }
}
ll pf[maxn + 1];
inline void get_f() {
    sieve();
    for(int i = 1; i <= maxn; i ++) {
        pf[i] = pf[i - 1] + f[i];
    }
}
inline ll calc(ll n, ll m) {
    ll ans = 0;
    ll bd = min(n, m);
    for(ll i = 1; i <= bd;) {
        ll next = min(n / (n / i), m / (m / i));
        next = min(next, bd);
        ll thi = (n / i) * (m / i) * (pf[next] - pf[i - 1]);
        ans += thi;
        i = next + 1;
    }
    return ans;
}
 
inline int readint() {
    int x = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}
inline void putint(ll x) {
    ll bf[30];
    int cnt = 0;
    if(!x) {
        bf[cnt ++] = 0;
    } else {
        while(x) {
            bf[cnt ++] = x % 10LL;
            x /= 10LL;
        }
    }
    for(int i = cnt - 1; i >= 0; i --) {
        putchar(bf[i] + '0');
    }
    putchar('\n');
}
int main() {
    get_f();
    int T; T = readint();
    while(T --) {
        int n, m;
        n = readint(); m = readint();
        putint(calc(n, m));
    }
    return 0;
}

然后我们大致就能归结出一个相当有用的式子:

\[\sum_{i = 1}^n \sum_{j = 1}^m p(gcd(i, j)) = 
\sum_{T = 1}^{min(n, m)} \lfloor\tfrac{n}{T}\rfloor\lfloor\tfrac{m}{T}\rfloor\sum_{d\mid T} p(d)\mu(\tfrac{T}{d})\]

这个推导,是蛮有用的。

Assam HS Syllabus Pd 说:
Sep 30, 2022 01:38:44 AM

Department of Education & Government of Assam Higher Secondary Education Council is announced the state class 11th and 12th standard Arts, Assam HS Syllabus Pdf Science and Commerce course students for MIL and revised course with Curriculum government and private college students as AHSEC HS Syllabus 2023 Pdf to all Hindi and English Medium students.Department of Education & Government of Assam Higher Secondary Education Council is announced the state class 11th and 12th standard Arts


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter