【題解】Kattis Coprime Integers

#include <iostream>
using namespace std;

const int maxn = 10000005;
int p[maxn], cnt[maxn];

long long solve(int x, int y){
    long long ret = (long long)x*y;
    for (int i = 2; i <= min(x, y); i++){
        if (cnt[i] < 0) continue;
        if (cnt[i] % 2 == 1) ret -= (long long)(x/i) * (y/i);
        else ret += (long long)(x/i) * (y/i);
    }
    return ret;
}

int main() {
    for (int i = 2; i < maxn; i++){
        if (!p[i]){
            cnt[i] = 1;
            for (int j = i*2; j < maxn; j+=i){
                p[j] = 1;
                cnt[j]++;
            }
            for (long long j = 1LL*i*i; j < maxn; j += i*i){
                cnt[j] = -10000005;
            }
        }
    }
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    long long ans = 0;
    ans = solve(b, d);
    ans -= solve(a-1, d);
    ans -= solve(b, c-1);
    ans += solve(a-1, c-1);
    cout << ans << "\n";
}