Chaos Slover 补档计划 - 数论函数变换(2)

2015.11.23 11:11 Mon| 10 visits oi_2016| ChaosSlover补档计划| Text

狄利克雷卷积

对于两个数论函数 $f_1$、$f_2$,称函数 $f(n)=\sum_{d|n}f_1(d)f_2(\frac{n}{d})$ 为 $f_1$ 和 $f_2$ 的狄利克雷卷积。

那么莫比乌斯反演的公式就可以表达为:

下面就算是一些化简的习题吧~

1D gcd sum

余数之和

使用前缀和+分块求解和式中的内容。

2D gcd sum

预处理欧拉函数的前缀和后分块计算。

zap

这前面的公式推起来都不是特别难啊……鬼畜的大概都在后面呢。

互质数和

推公式可真是辛苦啊!一直以为 $\sum_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}$ 这个公式没有用,竟然在这里用上了!

1D lcm sum

这公式推得要多辛苦有多辛苦啊,过程中还用到了上一题的结论。

实在是受够了推这种公式,还是感性一下吧……

设 $f(x)=\frac{1}{x}$,$F(x)=f\times\mu$ 利用莫比乌斯反演一顿神推,得到了另一个公式:

为了看懂这个推公式的过程真的是废了我不知道多少脑细胞,然而到这种地步仍然不会写代码……

2D lcm sum

BZOJ2154 Crash的数字表格

单组测试数据,时间复杂度 O(N)。

设 $f(x,y)=\sum_{i=1}^x\sum_{j=1}^y i*j*e(\gcd(i,j))$,于是我们有 $ans=\sum_{d=1}^{\min(n,m)}d*f(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)$,分块枚举 f 的参数。

设 $F(x,y)=\sum_{i=1}^x\sum_{j=1}^y i*j$,$f(x,y)=\sum_{i=1}^{\min(n,m)}i^2*\mu(i)*F(\lfloor\frac{x}{i}\rfloor,\lfloor\frac{y}{i}\rfloor)$

1

BZOJ2693 jzptab

多组测试数据,对于每组测试数据时间复杂度 O(sqrt(N))。

要线性筛的是这样一个好麻烦的式子 $f(x)=\sum_{i|x}i^2\mu(i)\frac{x}{i}$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

#define N 10000005
#define mod 100000009

int test, n, m;
int tot, p[N], v[N], sum[N];

void sieve(int n)
{
    sum[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (!v[i]) p[++tot] = i, sum[i] = (i - 1ll * i * i % mod + mod) % mod;
        for (int j = 1; i * p[j] <= n; ++j)
        {
            v[i * p[j]] = true;
            sum[i * p[j]] = 1ll * sum[i] * p[j] % mod;
            if (i % p[j] == 0) break;
            sum[i * p[j]] = (sum[i * p[j]]
                - 1ll * sum[i] * p[j] % mod * p[j] % mod + mod) % mod;
        }
    }
    for (int i = 1; i <= n; ++i)
        sum[i] = (sum[i] + sum[i - 1]) % mod;
}

long long getsum(int n, int m)
{
    return (1ll * n * (n + 1) / 2) % mod * (1ll * m * (m + 1) / 2 % mod) % mod;
}

int getans(int n, int m)
{
    if (n > m) swap(n, m);
    long long re = 0;
    for (int last = 0, i = 1; i <= n; i = last + 1)
    {
        last = min(n / (n / i), m / (m / i));
        re += getsum(n / i, m / i) * (sum[last] - sum[i - 1] + mod) % mod;
    }
    return re % mod;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    sieve(10000000);
    cin >> test;
    while (test--)
    {
        n = read(), m = read();
        printf("%d\n", getans(n, m));
    }
    return 0;
}

2D lcm sum EXT