NOIP2009 提高组 Hankson 的趣味题

欧拉筛 分解质因数 枚举约数 最大公因数与最小公倍数 DFS T4
P1072 [NOIP2009 提高组] Hankson 的趣味题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

Hanks 博士是 BT（Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。

今天在课堂上，老师讲解了如何求两个正整数 $c_1$ 和 $c_2$ 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 $a_0,a_1,b_0,b_1$，设某未知正整数 $x$ 满足：

1. $x$ 和 $a_0$ 的最大公约数是 $a_1$；

2. $x$ 和 $b_0$ 的最小公倍数是 $b_1$。

Hankson 的“逆问题”就是求出满足条件的正整数 $x$。但稍加思索之后，他发现这样的 $x$ 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 $x$ 的个数。请你帮助他编程求解这个问题。

输入格式

第一行为一个正整数 $n$，表示有 $n$ 组输入数据。接下来的$n$ 行每行一组输入数据，为四个正整数 $a_0,a_1,b_0,b_1$，每两个整数之间用一个空格隔开。输入数据保证 $a_0$ 能被 $a_1$ 整除，$b_1$ 能被 $b_0$ 整除。

输出格式

共 $n$ 行。每组输入数据的输出结果占一行，为一个整数。

对于每组数据：若不存在这样的 $x$，请输出 $0$，若存在这样的 $x$，请输出满足条件的 $x$ 的个数；

样例 #1

样例输入 #1

2 
41 1 96 288 
95 1 37 1776

样例输出 #1

6 
2

提示

【样例解释】

第一组输入数据，$x$ 可以是 $9,18,36,72,144,288$，共有 $6$ 个。

第二组输入数据，$x$ 可以是 $48,1776$，共有 $2$ 个。

【数据范围】

• 对于 $50\%$ 的数据，保证有 $1\le a_0,a_1,b_0,b_1\le 10000$ 且 $n\le 100$。
• 对于 $100\%$ 的数据，保证有 $1\le a_0,a_1,b_0,b_1\le 2\times 10^9$ 且 $n\le 2000$。

NOIP 2009 提高组 第二题

思路

求满足 $gcd(x,a_0)=a_1$ , $lcm(x,b_0)=b_1$ 的 $x$ 个数。

根据 $lcm(x,b_0)=b_1$ , 则 $x$ 一定是 $b_1$ 的约数, 可以直接枚举所有约数然后判断是否成立。且 2e9 的范围内的约数个数最多也只有 1536 个约数。

此时 $gcd(x,a_0)=a_1$ 可以直接判断, $lcm(x,b_0)=b_1$ 可以通过 $\frac{x\times b_0}{gcd(x,b_0)}=b_1$ 来判断。 这两步的时间复杂度为 $O(\log n)$。

因此对于每组数据可以用 $1600\times \log n\times 2000$ 大概是 $3.2\times 10^6\times \log n$ 大概也就 1e7 来判断, 够用。

但是在枚举 $b_1$ 的所有约数时, 按照之前的枚举思路, 最坏就是 $\sqrt{n}$ 的复杂度。

已经足够好了, 这里再加个小优化： 枚举时不要枚举所有数, 而是先将 $b_1$ 分解成质因数, 直接枚举所有质数来构成其分解质因式。

因为 $\sqrt{n}\approx 50000$, 其质数个数有 $\frac{50000}{\ln 50000}\approx 4621$ 个, 再用DFS爆搜出所有的约数, INT范围内总共最大也就1600, 故基本忽略不记。

这种优化就可以快十倍, 让原本 $5e4\times 2e3=1e8$ 的复杂度变成 $5e3\times 2e3=1e7$, 基本就可以过了。

代码

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];
 
struct Factor
{
    int p, s;
} factor[1601];
int fcnt;
 
int dividor[N], dcnt;
 
void init()
{
    for (int i = 2; i < N; i++)
    {
        if (!st[i])
            primes[cnt++] = i;
        for (int j = 0; primes[j] * i < N; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}
 
void dfs(int u, int p)
{
    if (u == fcnt)
    {
        dividor[dcnt++] = p;
        return;
    }
 
    for (int i = 0; i <= factor[u].s; i++)
    {
        dfs(u + 1, p);
        p = factor[u].p * p;
    }
}
 
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
 
void solve()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
 
    fcnt = 0;
    int t = d;
    for (int i = 0; primes[i] <= t / primes[i]; i++)
    {
        int p = primes[i];
        if (t % p == 0)
        {
            int c = 0;
            while (t % p == 0)
                t /= p, c++;
            factor[fcnt++] = {p, c};
        }
    }
    if (t > 1)
        factor[fcnt++] = {t, 1};
 
    // DFS搜约数
    dcnt = 0;
    dfs(0, 1);
 
    int res = 0;
    for (int i = 0; i < dcnt; i++)
    {
        int x = dividor[i];
        if (gcd(x, a) == b && (LL)x * c / gcd(x, c) == d)
            res++;
    }
    cout << res << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}