题目描述
Hanks
博士是 BT
(Bio-Tech
,生物技术)领域的知名专家,他的儿子名叫 Hankson
。
现在,刚刚放学回家的 Hankson
正在思考一个有趣的问题。
今天在课堂上,老师讲解了如何求两个正整数 $c _ 1$ 和 $c _ 2$ 的最大公约数和最小公倍数。
现在 Hankson
认为自己已经熟练地掌握了这些知识,他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”,这个问题是这样的:
已知正整数 $a _ 0, a _ 1, b _ 0, b _ 1$,设某未知正整数 $x$ 满足:
- $x$ 和 $a _ 0$ 的最大公约数是 $a _ 1$;
- $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 \le n \le 2000,$
$1 \le a _ 0, a _ 1, b _ 0, b _ 1 \le 2 \times 10 ^ 9$
输入样例:
2
41 1 96 288
95 1 37 1776
输出样例:
6
2
解题思路
首先观察到 $x$ 必定为 $ b _ 1$ 的因数,于是我们考虑对 $b _ 1$ 的每一个质因数的个数进行分析。
对于任意 $b _ 1$ 的质因数 $p$,设 $a _ 0, b _ 0, a _ 1, b _ 1, x$(注意 $b _ 0$ 和 $a _ 1$ 的位置)分别有 $m _ a, m _ b, m _ c, m _d, m _ x$ 个 $p$。
《算法竞赛进阶指南》一书中给出了如下分类:
在 $\gcd (a _ 0, x) = a _ 1$ 中:
- 若 $m _ a > m _ c$,则 $m _ x = m _ c$;
- 若 $m _ a = m _ c$,则 $m _ x \ge m _ c$;
- 若 $m _ a < m _ c$,则 $m _ x$ 无解。
在 $\text {lcm} (b _ 0, x) = b _ 1$ 中:
- 若 $m _ b < m _ d$,则 $m _ x = m _ d$;
- 若 $m _ b = m _ d$,则 $m _ x \le m _ d$;
- 若 $m _ b > m _ d$,则 $m _ x$ 无解。
结合上述两种情况,有以下结论:
- 若 $m _ a > m _ c, m _ b < m _ d, m _ c = m _ d$,则 $m _ x$ 只有一种取法,即 $m _ x = m _ c = m _ d$;
- 若 $m _ a > m _ c, m _ b = m _ d, m _ c \le m _ d$,则 $m _ x$ 只有一种取法,即 $m _ x = m _ c$;
- 若 $m _ a = m _ c, m _ b < m _ d, m _ c \le m _ d$,则 $m _ x$ 只有一种取法,即 $m _ x = m _ d$;
- 若 $m _ a = m _ c, m _ b = m _ d, m _ c \le m _ d$,则 $m _ x$ 有 $m _ d - m _ c + 1$ 种取法,即 $m _ x$ 可取 $[m _ c, m _ d]$ 中的任意值;
- 其他情况,$m _ x$ 有 $0$ 种取法,即 $m _ x$ 无解。
我们把 $m _ x$ 的取法个数记为 $cnt _ p$,根据乘法原理,$x$ 的数量为 $\prod \limits _ {质数 p | d} cnt _ p$ 种。
为了高效地计算,我们可以预处理出 $1 \sim \sqrt {2 \times 10 ^ 9}$ 的质数,来找出 $d$ 的质因数。
如果 $b _ 1$ 不是 $a _ 1$ 的倍数要特判,不然最后一个点过不去。
时间复杂度
约为 $\Theta (\frac {n \sqrt d} {\log d})$。
#include <iostream>
#define P 10005
using namespace std;
int n, a, b, c, d, tot, ans, prime[P];
bool v[P];
bool check (int x) // 判定质数
{
for (int i = 2; i * i <= x; i ++)
{
if (x % i == 0)
{
return 0;
}
}
return 1;
}
void primes () // 预处理质数
{
for (int i = 2; i * i <= 2e9; i ++)
{
if (check (i))
{
prime[++ tot] = i;
}
}
return ;
}
int how (int x, int y) // 几个质因数
{
int res = 0;
while (x % y == 0)
{
x /= y, res ++;
}
return res;
}
void calc (int p) // 计算每个质因数 p
{
int ma = how (a, p), mb = how (b, p), mc = how (c, p), md = how (d, p);
if (ma > mc && mb < md && mc == md)
{
return ;
}
if (ma > mc && mb == md && mc <= md)
{
return ;
}
if (ma == mc && mb < md && mc <= md)
{
return ;
}
if (ma == mc && mb == md && mc <= md)
{
ans *= md - mc + 1;
return ;
}
ans = 0;
return ;
}
int main ()
{
cin >> n, primes ();
while (n --)
{
cin >> a >> c >> b >> d, ans = !(d % c);
for (int i = 1; i <= tot; i ++)
{
if (d % prime[i] == 0)
{
calc (prime[i]), v[i] = 1;
while (d % prime[i] == 0)
{
d /= prime[i];
}
}
}
if (d > 1)
{
calc (d);
}
cout << ans << endl;
}
return 0;
}
ans = !(d % c);
为什么要这样赋初值?
可以优化
nb