[数据结构与算法]Mobius函数（模板）

AcWing215. 破译密码

题意

$对于给定的整数a,b和d，有多少正整数对x,y，满足x\le a，y\le b，并且gcd(x,y)=d。$

$(1\le n\le 50000,1\le d\le a,b\le 50000)$

证明：见acwing题解

或者《算法竞赛进阶指南》数论部分$P_{142}$页

#include<bits/stdc++.h>
using namespace std;
const int N = 50010;
typedef long long ll;
int v[N];
int prime[N], mobius[N], sum[N], m;
//线性筛写法
void Mobius() {
    mobius[1] = 1;
    m = 0;
    for (int i = 2; i < N; i++)
    {
        if (!v[i]) {
            v[i] = i;
            prime[++m] = i;
            mobius[i] = -1;
        }
        for (int j = 1; j <= m; j++)
        {
            if (prime[j] > v[i] || prime[j] > N / i) break;
            int t = prime[j] * i;
            v[t] = prime[j];
            if (i % prime[j] == 0) mobius[t] = 0;
            else mobius[t] = mobius[i] * -1;
        }
    }
    for (int i = 1; i < N; ++i) sum[i] = sum[i - 1] + mobius[i];//求前缀和，优化时间
}
//埃氏筛写法
void Mobius2()
{
    for (int i = 1; i < N; i++) mobius[i] = 1, v[i] = 0;
    for (int i = 2; i < N; i++)
    {
        if (v[i]) continue;
        mobius[i] = -1;
        for (int j = 2 * i; j < N; j += i)
        {
            v[j] = 1;
            if ((j / i) % i == 0) mobius[j] = 0;
            else mobius[j] *= -1;
        }
    }
    for (int i = 1; i < N; i++) sum[i] = sum[i - 1] + mobius[i];
}
int main() {
    Mobius();
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int a, b, d, m, n;
        scanf("%d%d%d", &a, &b, &d);
        a /= d, b /= d;
        n = min(a, b);
        ll res = 0;
        for (int l = 1, r; l <= n; l = r + 1)
        {
            r = min(n, min(a / (a / l), b / (b / l)));
            res += (sum[r] - sum[l - 1]) * 1ll * (a / l) * (b / l);//注意处理运算过程爆int
        }
        printf("%lld\n", res);
    }
    return 0;
}