传送门

看了1个多小时，终于懂了一点了

题目大意：给n,m,k.求gcd(x,y) = k(1<=x<=n, 1<=y<=m)的个数

思路：令F(i)表示i|gcd(x,y)的(x,y)的对数，显然F(x)=[nx]∗[mx]。

设f(x)为gcd(x,y)=x的对数。

因为F(x)=∑i|xf(i)，所以我们可以莫比乌斯反演它。

根据公式f(x)=∑x|dμ(d)F(d)

我们的目标就是f(1)（因为n和m都可以除以k）

所以我们就可以在O(n)的时间复杂度内求出答案了。

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 100005

int n, m, k, miu[MAXN], p[MAXN], cnt;

bool vis[MAXN];

void sieve() {

    miu[1] = 1;

    for(int i = 2; i < MAXN; ++ i) {

        if(!vis[i]) {

            miu[i] = -1;

            p[++ cnt] = i;

        }

        for(int j = 1; j <= cnt; ++ j) {

            if(p[j] * i > MAXN) break;

            vis[p[j]*i] = 1;

            if(i % p[j] == 0) {

                miu[i * p[j]] = 0;

                break;

            }

            else miu[i * p[j]] = - miu[i];

        }

    }

}

int main() {

    sieve(); int T, a, c; scanf("%d", &T);

    for(int C = 1; C <= T; ++ C) {

        printf("Case %d: ", C);

        scanf("%d%d%d%d%d", &a, &n, &c, &m, &k);

        if(!k) { puts("0"); continue; }

        n /= k; m /= k;

        if(n > m) swap(n, m);

        long long ans1 = 0, ans2 = 0;

        for(int i = 1; i <= n; ++ i)

            ans1 += 1LL * miu[i] * (n/i) * (m/i);

        for(int i = 1; i <= n; ++ i)

            ans2 += 1LL * miu[i] * (n/i) * (n/i);

        //因为要求无序的数对，所以我们可以减去ans2/2

        ans1 -= ans2/2;

        printf("%I64d\n", ans1);

    }

}