[BZOJ 2671]Calc 莫比乌斯函数

题目大意

给出N，统计满足下面条件的数对(a,b)的个数：
1.1≤a<b≤N
2.a+b整除a*b

解题报告

首先这道题的复杂度是不对的…

反正能过qwq。

我觉得 这位dalao的题解 写得非常妙啊, 当然同时安利一下看我的题解…

首先考虑题目给出的条件, [latex](a+b)|ab[/latex]
设\(d=gcd(a,b)\), 那么有:$$ \frac{a+b}{d} | \frac{ab}{d} $$

接下来证明当\( a \)和\(b\)互质时, \(a+b\)和\(ab\)互质:

设\(a\)和\(b\)互质且\(a+b\)和\(ab\)有公共质因子\(k\), 那么有\(k|a\)或者\(k|b\)。
假设\(k|a\)那么可得$$a=qk \Rightarrow a+b = qk+b \Rightarrow k|(qk+b) \Rightarrow k|b \Rightarrow k|gcd(a,b)$$
假定不成立, \(a+b\)和\(ab\)必须互质。

继续化简条件, 设[latex]a=\frac{a}{d}, b=\frac{b}{d}[/latex]:
$$ (a+b) | abd $$
由(a+b)和ab互质可得:
$$ (a+b) | d $$

由于\(b*d\le N \)并且\((a+b)|d\), 所以\(b\le m, m=\sqrt{N}\), 题目等价于统计:
$$ \sum_{b=1}^{m}\sum_{a=1}^{b-1}[gcd(a, b) == 1]\lfloor \frac{N}{b(a+b)} \rfloor $$

接下来利用 莫比乌斯函数 进行化简关键一步!
根据莫比乌斯函数性质有$$ (\sum_{d|n}\mu(d)) = [n == 1] $$
那么用这个性质代替gcd(a, b)等于1的约束, 化成:
$$ \sum_{b=1}^{m}\sum_{a=1}^{b-1}(\lfloor \frac{N}{b(a+b)} \rfloor \sum_{d|gcd(a, b)}\mu(d)) $$
枚举\(gcd(a, b)\)因子\(d\), 设\(a=d\cdot a, b=b\cdot d\), 将后面一坨提前:
$$ \sum_{d=1}^m \sum_{b=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{a=1}^{b-1} \lfloor \frac{N}{d^2b(a+b)} \rfloor $$
最后一坨[latex]\lfloor \frac{N}{d^2b(a+b)} \rfloor[/latex]只有[latex]\sqrt{N}[/latex]种取值, 分段计算, 暴力搞就可以了。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
inline int getInt () {
    int ret; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0');
    return flg ? -ret : ret;
}
const int MAXN = 100010;
int mu[MAXN], prec[MAXN/3], ptot;
bool isnprime[MAXN];
inline void linerShaker () {
    mu[1] = 1;
    for(int i = 2; i<MAXN; i++) {
        if(!isnprime[i]) {
            prec[++ptot] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= ptot && (LL)i*prec[j] < MAXN; j++) {
            isnprime[i*prec[j]] = true;
            if(i%prec[j] == 0) break ;
            mu[i*prec[j]] = -mu[i];
        }
    }
}
int main () {
    LL ans = 0;
    linerShaker();
    int N = getInt(), M = floor(sqrt(N));
    for(int d = 1; (LL)d<=M; d++) {
        LL tmp = 0;
        for(int b = 2; (LL)b*d<=M; b++) {
            // t = a+b
            for(int t = b+1; t<(b<<1); t++) {
                if(N/((LL)d*d*b*t) == 0) break;
                LL nxt = min((LL)(b<<1)-1, (N/(N/((LL)d*d*b*t)))/(d*d*b));
                tmp += (nxt-t+1)*(N/((LL)d*d*b*t));
                t = nxt;
            }
        }
        ans += mu[d]*tmp;
    }
    cout << ans << endl;
}