【题解】BZOJ 2694 Lcm

请注意,本文编写于 91 天前,最后修改于 91 天前,其中某些信息可能已经过时。

Problem

$$ \sum_{i=1}^{A}\sum_{j=1}^{B}lcm(i,j)[\forall n>1,n^2\nmid gcd(i,j)] \bmod 2^{30} $$

Thought

Crash 的数字表格 有些相似,多了一个 $\forall n>1,n^2\nmid gcd(i,j)​$ 的条件
那么考虑将所有 $\forall n>1,n^2\nmid gcd(i,j)​$ 的筛掉,按照原题的方法做就好了

但是显然不会用这么 naive 的做法,考虑如何去掉这个限制

根据莫比乌斯函数的性质有:若有 $\forall n>1,n^2\nmid x$ ,则 $\mu(x)=0$ ,否则 $\mu(x)=-1$ 或者 $\mu(x)=1$

那么将限制转化为 $\mu(gcd(i,j))^2​$

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

$$ \sum_{d=1}^n\sum_{i=1}^{n}\sum_{j=1}^{m}\mu(d)^2\frac{ij}{d}[gcd(i,j)=d] $$

$$ \sum_{d=1}^n\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}\mu(d)^2dij[gcd(i,j)=1] $$

考虑用 $\sum_{t|gcd(i,j)}\mu(t)$ 替代 $[gcd(i,j)=1]​$

$$ \sum_{d=1}^n\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}\mu(d)^2dij\sum_{t|gcd(i,j)}\mu(t) $$

$$ \sum_{d=1}^{n}d\mu(d)^2\sum_{t=1}^{\frac{n}{d}}t^2\mu(t)\sum_{i=1}^{\frac{n}{td}}\sum_{j=1}^{\frac{m}{td}}ij $$

$$ \sum_{d=1}^{n}d\mu(d)^2\sum_{t=1}^{\frac{n}{d}}t^2\mu(t)sum(\frac{n}{td})sum(\frac{m}{td}) $$

由于 $sum(\frac{n}{td})sum(\frac{m}{td}$ 中的 $td$ 不太好处理,考虑使 $T=td$ ,并且枚举 $T$
相应的, $d$ 变为 $T$ 的因数

$$ \sum_{T=1}^{n}\sum_{d|T}d\mu(d)^2(\frac{T}{d})^2\mu(\frac{T}{d})sum(\frac{n}{T})sum(\frac{m}{T}) $$

$$ \sum_{T=1}^{n}sum(\frac{n}{T})sum(\frac{m}{T})\sum_{d|T}d\mu(d)^2(\frac{T}{d})^2\mu(\frac{T}{d}) $$

$$ \sum_{T=1}^{n}sum(\frac{n}{T})sum(\frac{m}{T})T\sum_{d|T}\mu(d)^2\mu(\frac{T}{d})\frac{T}{d} $$

如何求得 $\sum_{d|T}\mu(d)^2\mu(\frac{T}{d})\frac{T}{d}​$ ?

这个显然是个积性函数
令 $f[x]=\sum_{d|x}\mu(d)^2\mu(\frac{x}{d})\frac{x}{d}$

首先需要求 $f[x],x=p^k$ 的情况

当 $k=1,f[x]=1-x$
当 $k=2,f[x]=-x$
当 $k>2$ 在 $\mu(d)$ 和 $\mu(\frac{x}{d})$ 中至少有一个有 $p^2$ 项,则为 $0$

那么就可以按照积性函数的性质来推啦!

至于模数就自然溢出呗

Code

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
ui read() {
    ui ans = 0;
    char ch = getchar();
    while(ch > '9' || ch < '0') ch = getchar();
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans;
}
const ui N = 4000010;
const ui mod = (1 << 30);
ui s[N], sum[N], f[N], pri[N], tot;
bool np[N];
void prepare() {
    s[1] = sum[1] = f[1] = 1;
    for(ui i = 2 ; i < N ; ++ i) {
        if(!np[i]) {
            pri[++ tot] = i;
            f[i] = 1 - i;
        }
        s[i] = s[i - 1] + f[i] * i;
        sum[i] = sum[i - 1] + i;
        for(ui j = 1 ; j <= tot && i * pri[j] < N ; ++ j) {
            np[i * pri[j]] = 1;
            if(i % pri[j])
                f[i * pri[j]] = f[i] * (1 - pri[j]);
            else {
                if(i % (pri[j] * pri[j]) == 0) f[i * pri[j]] = 0;
                else f[i * pri[j]] = - f[i / pri[j]] * pri[j];
                break;
            }
        }
    }
}
int main() {
    prepare();
    ui t = read();
    while(t --) {
        ui n = read(), m = read();
        if(n > m) swap(n, m);
        ui pos = 0, ans = 0;
        for(ui i = 1; i <= n; i = pos + 1) {
            pos = min(n / (n / i), m / (m / i));
            ans += (s[pos] - s[i - 1]) * sum[n / i] * sum[m / i];
        }
        printf("%u\n", ans & (mod - 1));
    }
    return 0;
}
Comments

添加新评论