[Algo Beat Contest 001 F] Foolish Math Homework 官方题解

· · 题解

原作者是 fcy。

设 ans 为给定值对应的答案，根据简单容斥得：

ans(a,b,c,d)=ans(1,b,1,d)-ans(1,a-1,1,d)-ans(1,b,1,c-1)+ans(1,c-1,1,d-1)

则问题转化为 1\le x \le n 且 1 \le y \le m，使得

y-x=\gcd(x,y)

同时除以 \gcd(x,y) 得

\frac{y}{\gcd(x,y)}-\frac{x}{\gcd(x,y)}=1

显然，\frac{x}{\gcd(x,y)} 与 \frac{y}{\gcd(x,y)} 为连续自然数。 则

\sum_{x=1}^n\sum_{y=1}^{m}[y-x=gcd(x,y)]=\sum_{g=1}^{\min(n,m)}\min(\frac{n}{g},\frac{m}{g}-1)

考虑数论分块，枚举区间 [l,r] 使得 \lfloor\frac{n}{l}\rfloor=\lfloor\frac{n}{r}\rfloor 且 \lfloor\frac{m}{l}\rfloor=\lfloor\frac{m}{r}\rfloor。则它对答案贡献为 \min(\lfloor\frac{m}{l}\rfloor-1,\lfloor\frac{n}{l}\rfloor)。

二维数论分块后求和即可，\sum_{g=1}^{\min(n,m)}\min(\frac{n}{g},\frac{m}{g}-1) 即为所求。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll calc(ll n, ll m) {
    ll t = min(n, m);
    ll l = 1, r, res = 0;
    while (l <= t) {
        r = min({n / (n / l), m / (m / l), t});
        ll a1 = n / l, a2 = m / l;
        res += min(a1, a2 - 1) * (r - l + 1);
        l = r + 1;
    }
    return res;
}

int main() {
    ll l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;
    cout << calc(l1 - 1, l2 - 1) + calc(r1, r2) - calc(l1 - 1, r2) - calc(r1, l2 - 1);
    return 0;
}