【題解】AtCoder ABC 206E – Divide Both

【題目敘述】https://atcoder.jp/contests/abc206/tasks/abc206_e
【解題想法】質數篩法

#include <iostream>
using namespace std;
 
const int maxn = 1000005;
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] = -1000005;
            }
        }
    }
    int l, r;
    cin >> l >> r;
    long long ans = (long long)(r-l+1)*(r-l+1);
    ans -= solve(r, r);
    ans += solve(l-1, r)*2;
    ans -= solve(l-1, l-1);
    for (int i = l; i <= r; i++){
        ans -= (r/i-1)*2+1;
    }
    if (l == 1){
        ans--;
        ans += (r-l+1)*2;
    }
    cout << ans << "\n";
}
分享本文 Share with friends