BZOJ2693 jzptab <莫比乌斯反演>

Problem

jzptab

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

求$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$，答案模$10^9+9$输出。
多组询问。

Input

一个正整数$T$表示数据组数。
接下来$T$行，每行两个正整数 表示$N,M$。

Output

$T$行，每行一个整数，表示第$i$组数据的结果。

Sample Input

1
4 5

Sample Output

122

HINT

$T\le 10^4$
$N,M\le 10^7$

Sourse

版权所有者：倪泽堃

标签：莫比乌斯反演

Solution

此题和$\mathrm{BZOJ2154}$所求相同，只是又多组询问，如果每次都像那$\mathrm{BZOJ2154}$样$O(n)$做为$\mathrm{TLE}$。故需要改变求和方式。这里将使用的最终推$\mathrm{BZOJ2154}$导结果来继续恒等变形。前面的推导见：BZOJ2154。

$$\begin{aligned} Ans&=\sum_{d=1}^{\min(n,m)}{d}\sum_{k=1}^{\min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\mu(k)\times k^2\times\frac{\lfloor\frac{n}{d\times k}\rfloor\times(\lfloor\frac{n}{d\times k}\rfloor+1)}{2}\times\frac{\lfloor\frac{m}{d\times k}\rfloor\times(\lfloor\frac{m}{d\times k}\rfloor+1)}{2}\\ &=\sum_{d=1}^{\min(n,m)}\sum_{t=k\times d(k\in\mathbb{N^*})}^{\min(n,m)}\mu(\frac{t}{d})\times\frac{t^2}{d^2}\times\frac{\lfloor\frac{n}{t}\rfloor\times(\lfloor\frac{n}{t}\rfloor+1)}{2}\times\frac{\lfloor\frac{m}{t}\rfloor\times(\lfloor\frac{m}{t}\rfloor+1)}{2}\times{d}\\ &=\sum_{t=1}^{\min(n,m)}{\frac{\lfloor\frac{n}{t}\rfloor\times(\lfloor\frac{n}{t}\rfloor+1)}{2}\times\frac{\lfloor\frac{m}{t}\rfloor\times(\lfloor\frac{m}{t}\rfloor+1)}{2}}\sum_{k|t}\mu(k)\times k^2\times\frac{t}{k}\\ \end{aligned}$$

$$\begin{aligned} &Let\;F(t)=\sum_{k|t}\mu(k)\times k^2\times \frac{t}{k}\ ,\\ &then\;S=\sum_{t=1}^{\min(n,m)}{\frac{\lfloor\frac{n}{t}\rfloor\times(\lfloor\frac{n}{t}\rfloor+1)}{2}\times\frac{\lfloor\frac{m}{t}\rfloor\times(\lfloor\frac{m}{t}\rfloor+1)}{2}}\times F(t)\\ \end{aligned}$$

$$\begin{aligned} &\because f(x)=\mu(x),\;g(x)=x^2,\;h(x)=\frac{t}{x}\;are\;all\;multiplicative\;functions\\ &\therefore F(x)=\sum_{t|x}f(t)\times g(t)\times h(t)\;is\;a\;multiplicative\;function\\ &\Longrightarrow We\;can\;use\;a\;Linear\;Seive\;to\;calculate\;F(x)\\ &If\;x\equiv1\sim y-1\mod{y}\;\;(y\;is\;a\;prime\;number)\\ &\;\;\;\;then\;F(x\times y)=F(x)\times F(y)\\ &If\;x\equiv0\mod{y}\;\;(y\;is\;a\;prime\;number)\\ &\;\;\;\;then\;\mu(x\times y)=0,\;F(x\times y)=F(x)\times y \end{aligned}$$

综上，$F(x)$的前缀和可用线性筛预处理，对于每次询问对$\frac{\lfloor\frac{n}{t}\rfloor\times(\lfloor\frac{n}{t}\rfloor+1)}{2}\times\frac{\lfloor\frac{m}{t}\rfloor\times(\lfloor\frac{m}{t}\rfloor+1)}{2}$根号分块，即可做到$O(T\sqrt{n})$的复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 10000000
#define MOD 100000009
using namespace std;
typedef long long lnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt n, m, cnt, ans, s[MAX_N+5], pri[MAX_N+5];    bool NotPri[MAX_N+5];
void init() {
    NotPri[1] = true, s[1] = 1;
    for (lnt i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, s[i] = (i-i*i%MOD)%MOD;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > MAX_N) break;
            NotPri[i*pri[j]] = true;
            if (i%pri[j]) s[i*pri[j]] = s[i]*s[pri[j]]%MOD;
            else {s[i*pri[j]] = s[i]*pri[j]; break;}
        }
    }
    for (int i = 1; i <= MAX_N; i++) (s[i] += s[i-1]) %= MOD;
}
int main() {
    int T;	read(T), init();
    while (T--) {
        lnt n, m;	read(n), read(m), ans = 0;
        for (lnt l = 1, r; l <= min(n, m); l = r+1)
            r = min(n/(n/l), m/(m/l)), (ans += (n/l*(n/l+1)/2%MOD)*(m/l*(m/l+1)/2%MOD)%MOD*(s[r]-s[l-1])%MOD) %= MOD;
        printf("%lld\n", (ans+MOD)%MOD);
    }
    return 0;
}