hdu-1695 GCD (莫比乌斯反演)

题意:

求 x 在[1, n]范围内,y 在[1, m]范围内的满足 gcd(x, y) = k 的x,y对数。

题解:
  • 如果f(k) 表示题目范围内gcd(x, y)=k 的对数,但是这个f(k)比较"难求"。我们发现gcd(x,y) %k == 0的x,y对数却很好求。我们先用 F(k) 表示 gcd(x,y) % k == 0 的对数。这时就想能不能用F(k) 去求 f(k)。毕竟 \(F(k) = \sum_{k|d} f(d)\) 这就可以用莫比乌斯反演公式得到

    \[f(k) = \sum_{k|d} \mu(\frac{d}{k})F(d) \]

    \[f(k) = \sum_{k|d} \mu(\frac{d}{k}) \lfloor\frac{n}{d}\rfloor \lfloor\frac{m}{d}\rfloor \]

    我们遍历所有d(d是k的倍数)去求和。因为如果\(gcd(x,y) = 1\),则\(gcd(k*x,k*y) = k\) 所以我们可以用上式求f(1)

    \[f(1) = \sum_{d=1}^{lim} \mu(d) \lfloor\frac{n}{d}\rfloor \lfloor\frac{m}{d}\rfloor \]

    因为k*x<=n, k * y <= m。所以lim = min(n/k, m/k)

    复杂度O(n)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;

int T, k, a, b, c, d;
int pri[N], cnt;
int mu[N];
int vis[N];

void prime(){
    mu[1] = 1;
    for(int i = 2; i <= 4e5; ++ i){
        if(!vis[i]){
            pri[++ cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= cnt && pri[j] * i <= 4e5; ++ j){
            vis[pri[j] * i] = 1;
            if(i % pri[j] == 0){
                mu[pri[j] * i] = 0;
                break;
            }
            mu[pri[j] * i] = -mu[i];
        }
    }
}


int main()
{
    prime();
    scanf("%d",&T);
    for(int Case = 1; Case <= T; ++ Case){
        scanf("%d%d%d", &b, &d, &k);
        if(!k){
            printf("0\n", Case);
            continue;
        }
        b /= k, d /= k;
        if(b > d) swap(b, d);
        ll ans = 0, ans1 = 0;
        for(int i = 1; i <= b; ++ i) ans += (ll)mu[i] * (b / i) * (d / i);
        for(int i = 1; i <= b; ++ i) ans1 += (ll)mu[i] * (b / i) * (b / i);
        ans -= ans1 / 2;
        printf("%lld\n", ans);
    }
    return 0;
}

题解博客: https://blog.csdn.net/litble/article/details/72804050?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

上一篇:CF1553F Pairwise Modulo


下一篇:洛谷 P2260 [清华集训2012]模积和