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

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

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

\[\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})\]

这个推导，是蛮有用的。

• 相关文章
• 全局相关文章