【題目敘述】https://open.kattis.com/problems/coprimeintegers
【解題想法】排容,質數篩法
#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";
}