「HAOI 2011」Problem b

#include <bits/stdc++.h>
using namespace std;
const int N = 50000;
int mu[N + 5], p[N + 5];
bool flg[N + 5];

void init() {
    int tot = 0;
    mu[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if (!flg[i]) {
            p[++tot] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= tot && i * p[j] <= N; ++j) {
            flg[i * p[j]] = 1;
            if (i % p[j] == 0) {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= N; ++i) mu[i] += mu[i - 1];
}

int solve(int n, int m) {
    int res = 0;
    for (int i = 1, j; i <= std::min(n, m); i = j + 1) {
        j = std::min(n / (n / i), m / (m / i));
        res += (mu[j] - mu[i - 1]) * (n / i) * (m / i);
    }
    return res;
}

int main() {
    int T, a, b, c, d, k;
    init();
    cin >> T;
    while (T--) {
        cin >> a >> b >> c >> d >> k;
        cout << solve(b / k, d / k)
                - solve(b / k, (c - 1) / k)
                - solve((a - 1) / k, d / k)
                + solve((a - 1) / k, (c - 1) / k) << endl;
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

namespace SOL {
    const int MAXN = 50011;
    const int MAXL = 50000;
    LL a, b, c, d, k, ans;
    int prime[MAXN], cnt;
    bool ok[MAXN];
    int mobius[MAXN], sum[MAXN]; //莫比乌斯函数及其前缀和

    inline void init() { //递推得到莫比乌斯函数
        //1的莫比乌斯函数是1；质数的莫比乌斯函数为1；含有相同质因子的数莫比乌斯函数为0；
        //不含有相同质因子的数的莫比乌斯函数函数为（-1）^k，k为质因子个数
        mobius[1] = 1;
        for (int i = 2; i <= MAXL; i++) {
            if (!ok[i]) {
                mobius[i] = -1;
                prime[++cnt] = i;
            }
            for (int j = 1; j <= cnt && i * prime[j] <= MAXL; j++) {
                ok[i * prime[j]] = 1;//标记合数
                if (i % prime[j]) mobius[i * prime[j]] = -mobius[i];//互质的两个数乘起来得到一个不含有相同质因子的数，质因子个数奇偶性改变，莫比乌斯函数变号
                else {
                    mobius[i * prime[j]] = 0;
                    break;
                }//留到后面再筛，此处已经可以break
            }
        }
        for (int i = 1; i <= MAXL; i++) sum[i] = sum[i - 1] + mobius[i];//求莫比乌斯函数的前缀和
    }

    inline LL solve(LL n, LL m) {//计算a在[1,n]且b在[1,m]中的gcd(a,b)==1的数目
        n /= k;
        m /= k;
        if (n > m) swap(n, m);
        if (n == 0) return 0;
        LL i, next1, next2, next;//把相等的部分直接分块一起计算
        LL tot = 0;
        for (i = 1; i <= n; i = next) {
            next1 = n / (n / i);
            next2 = m / (m / i);
            next = min(next1, next2);
            tot += (n / i) * (m / i) * (sum[next] - sum[i - 1]);
            next++;
        }
        return tot;
    }

    inline void work() {
        int T;
        cin >> T;
        init();
        while (T--) {
            cin >> a >> b >> c >> d >> k;
            ans = solve(b, d) - solve(a - 1, d) - solve(b, c - 1) + solve(a - 1, c - 1);//容斥原理
            cout << ans << endl;
        }
    }
}

int main() {
    SOL::work();
    return 0;
}