BZOJ2671 Calc <莫比乌斯反演>

Problem

Calc

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

Description

给出$N$，统计满足下面条件的数对$(a,b)$的个数：

• $1\le a<b\le N$
• $(a+b)|(a\cdot b)$

Input

一行一个数$N$。

Output

一行一个数表示答案。

Sample Input

15

Sample Output

4

HINT

测试点编号</font color=#000000>	数据规模</font color=#000000>	测试点编号</font color=#000000>	数据规模</font color=#000000>
$01$	$N\le 10$	$11$	$N\le 5\times 10^7$
$02$	$N \le 50$	$12$	$N\le 10^8$
$03$	$N\le 10^3$	$13$	$N\le 2\times 10^8$
$04$	$N\le 5\times 10^3$	$14$	$N\le 3\times 10^8$
$05$	$N\le 2\times 10^4$	$15$	$N\le 5\times 10^8$
$06$	$N\le 2\times 10^5$	$16$	$N\le 10^9$
$07$	$N\le 2\times 10^6$	$17$	$N\le 10^9$
$08$	$N\le 10^7$	$18$	$N\le 2^{31}-1$
$09$	$N\le 2\times 10^7$	$19$	$N\le 2^{31}-1$
$10$	$N\le 3\times 10^7$	$20$	$N\le 2^{31}-1$

标签：莫比乌斯反演

Solution

一道稍有变形的莫比乌斯反演，$blutrex$有$O(n^{\frac{3}{4}})$的算法，但我只会小常数的$O(n)$算法，不过可以过$BZOJ$数据。

问题即求$\sum_{i=1}^{n}\sum_{j=i+1}^{n}{[(i+j)|(i\times j)]}$的值。设$\gcd(i,j)=d$, $i=x\times d$, $j=y\times d$，易知$\gcd(x,y)=1$。
那么$(i+j)|(i\times j)$$\iff$$((x+y)\times d)|(x\times y\times d^2)$$\iff$$(x+y)|(x\times y\times d)$$\iff$$(x+y)|d$。
不妨设$d=k\times(x+y)$，那么$a=x\times d=k\times x\times(x+y)$, $b=y\times d=k\times y\times(x+y)$。
有

\begin{equation} \begin{aligned} 原式 =& \sum_{x=1}^{n}\sum_{y=x+1}^{n}[\gcd(x,y)=1\ \&\&\ a<b\le n]\\ =& \sum_{y=1}^{\lfloor\sqrt{n}-1\rfloor}\sum_{x=1}^{y-1}\sum_{k\in \mathbb{Z}^*}{[\gcd(x,y)=1\ \&\&\ k\times y\times (x+y)\le n]}\\ =& \sum_{y=1}^{\lfloor\sqrt{n}-1\rfloor}\sum_{x=1}^{y-1}[\gcd(x,y)=1]\times \lfloor\frac{n}{y\times(x+y)}\rfloor\\ \end{aligned} \end{equation}

显然$val=\lfloor\frac{n}{y\times(x+y)}\rfloor$只有$\sqrt{n}$级别种取值，可以根号分块来算，即枚举$y$，每次找到$val$相等的一段$x\in[lo,hi]$，统计$[lo,hi]$间满足$\gcd(x,y)=1$的$x$的个数，可以套用基础莫比乌斯反演公式，即$\sum_{d|y}{\mu(d)\cdot(\lfloor\frac{hi}{d}\rfloor-\lfloor\frac{lo-1}{d}\rfloor)}$。

此算法先枚举$y$的取值，再枚举$val$的取值，最后枚举$y$的约数$d$计算反演。其中$y$有$\sqrt{n}$级别种取值，$val$所对应的$[lo,hi]$都在$(0,y)$之间，即共有$\sqrt{y}\thickapprox\sqrt[4]{n}$级别种取值，而最后的$d$又有$\sqrt{y}\thickapprox\sqrt[4]{n}$级别种取值，故总时间复杂度应为$O(n)$。但是由于$val$的取值总数通常到不了$\sqrt[4]{n}$级别，且$d$的取值总数通常也到不了$\sqrt[4]{n}$级别，因此常数非常小，跑得贼快，可以过此题$2\times 10^9$级别的数据。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
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');
}
int pri[MAX_N+5], mu[MAX_N+5], fac[MAX_N+5], cnt;    bool NotPri[MAX_N+5];
void PriS() {
    mu[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1;
        for (int j = 0, x; j < cnt; j++) {
            if ((x = i*pri[j]) > MAX_N) break;
            NotPri[x] = true;
            if (i%pri[j]) mu[x] = -mu[i];
            else {mu[x] = 0;	break;}
        }
    }
}
int main() {
    int n;	read(n), PriS();	lnt ans = 0LL;
    for (lnt i = 1, l, r; i < sqrt(n); i++) {
        cnt = 0; for (int j = 1; j <= sqrt(i); j++) if (i%j == 0) fac[cnt++] = j;
        for (l = 1; l < i; l = r+1) {
            lnt val = n/(i*(i+l)); if (!val) break;	r = min(n/val/i-i, i-1);
            for (lnt k = 0, j; k < cnt; k++) {
                j = fac[k], ans += mu[j]*(r/j-(l-1)/j)*val;	lnt t = i/j;
                if (i%t == 0 && (j^t)) ans += mu[t]*(r/t-(l-1)/t)*val;
            }
        }
    }
    return printf("%lld\n", ans), 0;
}