洛谷 P1390 公约数的和 题解
例题
给定$n\ \ (2\leq n\leq 2\mathrm{e}6)$,求$\displaystyle \sum_{i=1}^n\sum_{j=i+1}^n \gcd(i,j)$.
思路
[定理1] $\displaystyle \sum_{i\leq n}\sum_{d\mid i}\mu(d)=\sum_{d\leq n}\left\lfloor\dfrac{n}{d}\right\rfloor\mu(d)$.
[证] $\displaystyle\sum_{i\leq n}\sum_{d\mid i}$表示先枚举$1\sim n$内的$i$,再枚举$i$的所有约数,
这等价于先枚举$1\sim n$内的$d$,再枚举其在$1\sim n$内的倍数,显然倍数有$\left\lfloor\dfrac{n}{d}\right\rfloor$个.
[定理2] $\displaystyle\sum_{i\leq n}\sum_{j\leq m}[\gcd(i,j)==1]=\sum_{d\leq\min\{n,m\}}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor$.
[证] 注意到$\displaystyle [\gcd(i,j)==1]=\sum_{d\mid \gcd(i,j)}\mu(d)$,
由定理1:$\displaystyle \mathrm{LHS}=\sum_{i\leq n}\sum_{j\leq m}\sum_{d\mid\gcd(i,j)}\mu(d)=\sum_{i\leq n}\sum_{j\leq m}\sum_{d\mid i}\sum_{d\mid j}\mu(d)=\sum_{i\leq n}\sum_{d\mid i}\sum_{j\leq m}\sum_{d\mid j}\mu(d)$.
由定理2:$\displaystyle =\sum_{d\leq n}\left\lfloor\dfrac{n}{d}\right\rfloor\sum_{d\leq m}\left\lfloor\dfrac{m}{d}\right\rfloor\mu(d)=\sum_{d\leq\min\{n,m\}}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor$.
为求$\displaystyle \sum_{i=1}^n\sum_{j=i+1}^n \gcd(i,j)$,先求$\displaystyle\sum_{i\leq n}\sum_{j\leq n}\gcd(i,j)$.
考虑枚举$d\in[1,n]$,则$\displaystyle\sum_{i\leq n}\sum_{j\leq n}\gcd(i,j)$等于$d$乘$\gcd(i,j)=d$的数的个数,即$\displaystyle\sum_{d\leq n}d\cdot \sum_{i\leq n}\sum_{j\leq n}[\gcd(i,j)==d]$.
$\displaystyle\sum_{d\leq n}d\cdot \sum_{i\leq n}\sum_{j\leq n}[\gcd(i,j)==d]=\sum_{d\leq n}d\cdot \sum_{i\leq\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j\leq\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(i,j)==1]\xlongequal{t=\frac{n}{d}}\sum_{d\leq n}d\cdot \sum_{d’\leq t}\mu(d’)\left\lfloor\dfrac{t}{d’}\right\rfloor^2$,用整除分块求即可.
对比$\displaystyle \sum_{i=1}^n\sum_{j=i+1}^n \gcd(i,j)$和$\displaystyle\sum_{i\leq n}\sum_{j\leq n}\gcd(i,j)$枚举的$(i,j)$对:
$\displaystyle \sum_{i=1}^n\sum_{j=i+1}^n \gcd(i,j)$ | $\displaystyle\sum_{i\leq n}\sum_{j\leq n}\gcd(i,j)$ | |
---|---|---|
$i=1$ | $j=2,3,\cdots,n$ | $j=1,2,\cdots,n$ |
$i=2$ | $j=3,4,\cdots,n$ | $j=1,2,\cdots,n$ |
$\vdots$ | $\vdots$ | $\vdots$ |
$i=n-1$ | $j=n$ | $j=1,2,\cdots,n$ |
$i=n$ | $\varnothing$ | $j=1,2,\cdots,n$ |
观察知:第$1\sim (n-1)$行后者都比前者多枚举了一倍,且后者比前者多了$i=n$的枚举.
$i=n$时,$\displaystyle\sum_{i\leq n}\sum_{j\leq n}\gcd(i,j)=\sum_{j\leq n}\gcd(n,j)=1+2+\cdots+n=\dfrac{n(n+1)}{2}$,这是因为$n$是$1\sim n$中最大的,则$\gcd(j,n)=\min\{j,n\}\ \ (1\leq j\leq n)$.
故$\displaystyle\sum_{i\leq n}\sum_{j\leq n}\gcd(i,j)=2\sum_{i=1}^n\sum_{j=i+1}^n \gcd(i,j)+\dfrac{n(n+1)}{2}$.
代码
const int MAXN = 2e6 + 5;
int n;
int primes[MAXN], cnt = 0;
bool vis[MAXN];
int mu[MAXN];
int pre[MAXN]; // mu[]的前缀和
void init() { // 预处理mu[]及其前缀和
mu[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (!vis[i]) primes[cnt++] = i, mu[i] = -1;
for (int j = 0; primes[j] * i < MAXN; j++) {
vis[primes[j] * i] = true;
if (i % primes[j] == 0) break;
mu[primes[j] * i] = -mu[i];
}
}
for (int i = 1; i < MAXN; i++) pre[i] = pre[i - 1] + mu[i];
}
ll cal(int n, int d) {
n /= d;
ll res = 0;
for (int l = 1, r = 0; l <= n; l = r + 1) {
int tmp = n / l;
r = min(n, n / tmp);
res += (ll)(pre[r] - pre[l - 1]) * tmp * tmp; // 注意ll
}
return res;
}
int main() {
init();
cin >> n;
ll ans = 0;
for (int d = 1; d <= n; d++) ans += (ll)d * cal(n, d);
ans -= (ll)n * (n + 1) / 2, ans >>= 1;
cout << ans;
}