Hankson的趣味题

解题思路

本题要求有多少个 $x$ 满足 $gcd(a_0, x) = a_1, lcm(b_0, x) = b_1$

从 $lcm(a_0, x) = a_1$，可知 $x$ 一定是 $a_1$ 的约数，因此我们可以用试除法求出 $a_1$ 的所有约数，注意判断是否满足这两个条件，但是这个方法的时间复杂度为 $O(n\sqrt{d}\log{d})$，本题的数据很大，会被卡，需要考虑进一步优化。

$d$ 的约数个数上界大约是 $1 \sim d$，并且是远远达不到这个上界的，实际上，$10^9$ 之内的自然数中，约数个数最多的自然数仅有 $1536$ 个约数。

为了尽量避免试除法中耗费大量时间，我们可以预处理出 $1 \sim \sqrt{2 \* 10^9}$ 之间的所有质数，然后用这些质数去将 $b_1$ 分解质因数，然后用 dfs 将分解出的所有质因数拼凑出所有的约数。

C++ 代码

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 50010;

int n;
int primes[N], cnt; //存储所有质数
bool st[N]; //记录每个数是不是合数
PII factor[N]; //存储 b1 的所有质因子及个数
int divider[N]; //记录 b1 的所有约数
int cntf, cntd;

void get_primes(int n) //线性筛法筛质数
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

void dfs(int u, int p) //dfs 用质因子拼凑所有约数
{
    if(u == cntf)
    {
        divider[cntd++] = p;
        return;
    }

    for(int i = 0; i <= factor[u].second; i++)
    {
        dfs(u + 1, p);
        p *= factor[u].first;
    }
}

int main()
{
    get_primes(50000); //预处理出 1 ~ sqrt(2 * 1e9) 之间的所有质数

    scanf("%d", &n);
    while(n--)
    {
        int a0, a1, b0, b1;
        scanf("%d%d%d%d", &a0, &a1, &b0, &b1);

        //将 b1 分解质因子并存入 factor
        int d = b1;
        cntf = 0;
        for(int i = 0; primes[i] <= d / primes[i]; i++)
        {
            int p = primes[i];
            if(d % p == 0)
            {
                int s = 0;
                while(d % p == 0) s++, d /= p;
                factor[cntf++] = {p, s};
            }
        }
        if(d > 1) factor[cntf++] = {d, 1};

        //用 d1 的所有质因子拼凑出 d1 的所有约数
        cntd = 0;
        dfs(0, 1);

        //枚举所有约数，记录满足条件的数的个数
        int res = 0;
        for(int i = 0; i < cntd; i++)
        {
            int x = divider[i];
            if(gcd(x, a0) == a1 && (LL)x * b0 / gcd(x, b0) == b1) res++;
        }
        printf("%d\n", res);
    }
    return 0;
}