Mobius函数(模板)

阎卓
2023-12-01

AcWing215. 破译密码

题意

对于给定的整数 a , b 和 d ,有多少正整数对 x , y ,满足 x ≤ a , y ≤ b ,并且 g c d ( x , y ) = d 。 对于给定的整数 a,b 和 d,有多少正整数对 x,y,满足 x≤a,y≤b,并且 gcd(x,y)=d。 对于给定的整数a,bd,有多少正整数对x,y,满足xayb,并且gcd(x,y)=d

( 1 ≤ n ≤ 50000 , 1 ≤ d ≤ a , b ≤ 50000 ) (1≤n≤50000,1≤d≤a,b≤50000) (1n50000,1da,b50000)

证明:见acwing题解

或者《算法竞赛进阶指南》数论部分 P 179 P_{179} P179

#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;
}
 类似资料: