本文共 1709 字，大约阅读时间需要 5 分钟。

为了解决问题，我们需要计算满足条件的数对 (x, y)，使得 1 ≤ x ≤ N，1 ≤ y ≤ M，且 gcd(x, y) 是素数。我们可以利用莫比乌斯函数和包含-排除原理来高效地解决这个问题。

方法思路

解决代码

#include 
   
    using namespace std;const int maxm = 1e6 + 5;int notprime[maxm];int prime[maxm], cnt;int mu[maxm];void Minit() {    mu[1] = 1;    for (int i = 2; i < maxm; ++i) {        if (!notprime[i]) {            prime[cnt++] = i;            mu[i] = -1;        }        for (int j = 0; j < cnt; ++j) {            if (prime[j] * i > maxm) break;            notprime[prime[j] * i] = 1;            mu[prime[j] * i] = (i % prime[j]) ? -mu[i] : 0;            if (i % prime[j] == 0) break;        }    }}int main() {    Minit();    int t;    cin >> t;    while (t--) {        int N, M;        cin >> N >> M;        if (N == 0 || M == 0) {            cout << 0 << endl;            continue;        }        long long ans = 0;        for (int p = 0; p < cnt; ++p) {            int current_p = prime[p];            long long sum_p = 0;            for (int k = 1; ; ++k) {                if ((long long)k * current_p > maxm) break;                if (mu[k] == 0) continue;                int multiple = current_p * k;                int a = N / multiple;                int b = M / multiple;                sum_p += mu[k] * a * b;            }            ans += sum_p;        }        cout << ans << endl;    }    return 0;}
   

代码解释

这种方法高效地利用了莫比乌斯函数和包含-排除原理，确保了计算的准确性和效率。

转载地址：http://qtzv.baihongyu.com/