Hankson 的趣味题——唯一分解定律
题目来源
题目描述
Hanks 博士是 BT (Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。
今天在课堂上，老师讲解了如何求两个正整数 c1 和 c2 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 a0,a1,b0,b1，设某未知正整数 x 满足：
1． x 和 a0 的最大公约数是 a1；
2． x 和 b0 的最小公倍数是 b1。
Hankson 的“逆问题”就是求出满足条件的正整数 x。但稍加思索之后，他发现这样的x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 x 的个数。请你帮助他编程求解这个问题。
输入输出格式
输入格式：
第一行为一个正整数 n，表示有 n 组输入数据。接下来的 n 行每行一组输入数据，为四个正整数 a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证 a0 能被 a1 整除，b1 能被 b0 整除。
输出格式：
输出文件 son.out 共 n 行。每组输入数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的 x，请输出 0；
若存在这样的 x，请输出满足条件的 x 的个数；
输入输出样例
输入样例#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≤a0，a1，b0，b1≤10000 且 n≤100。
对于 100%的数据，保证有 1≤a0，a1，b0，b1≤2,000,000,000 且 n≤2000。
NOIP 2009 提高组 第二题
解题报告
首先我们考虑 最大公因数 和 最小公倍数 的 分解质因数 求法：
对于 a 和 b ，我们将其分解质因数。
如果对于每一个底数，我们均取对应最小的指数，那么得到的结果就是这两个数的最大公因数。
如果对于每一个底数，我们均取对应最大的指数，那么得到的结果就是这两个数的最小公倍数。
从 最大公因数 和 最小公倍数 的 分解质因数 求法中我们可以推导出，如果两个数 a 和 b ，他们的最大公因数是 c 。将 a ， b ， c 均分解质因数，可知如果第 i 个 质因子 在 b 和 c 分解质因数后得到的指数不同，那么 a 在分解质因数后 第 i 个 质因子 的指数一定与 c 分解质因数后对应位置的指数相同。如果 第 i 个质因子 在 b 和 c 分解质因数后得到的指数相同，那么 a 在分解质因数后对应位置的指数一定大于等于该值。
同理我们也可以推出最小公倍数中的对应关系，在这里不再赘述。
那么现在我们的目标就是求出各个数对应的质因数分解，但是我们发现 a0, a1, b0, b1 的范围在 2,000,000,000 以内，很明显我们无法直接求出 2,000,000,000 以内的所有质数。但是我们可以求出 √(2,000,000,000) 以内的所有质数，他们的最大值一定小于 45000。
如果我们需要分解一个大于等于 45000 的数字，我们首先需要通过 45000 以内的所有质数对其分解，当所有 45000 以内的质数对其分解结束之后，剩余的数一定是一个大质数。这是因为如果剩余的数是一个合数，那么这个合数一定可以进行质因数分解，由于最小的质数是 2， 所以如果存在这个合数那么 这个合数一定可以通过 45000 以内的质数进行质因数分解，但是我们已经将所有 45000 以内的质数对其进行分解了，这说明剩余的数一定不是一个合数，那就是一个大质数了，因此我们只需要再将这个数加入到预先处理处的素数表的末尾，并将其对应的指数记为 1 即可。
源代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
long long a, b, c, d;
int A[45005], B[45005], C[45005], D[45005];// a b c d 对应的质因数分解
int prime[100001], size;
bool notPrime[100001];
int analyse (int * map, long long num) { // 将 num 进行质因数分解
for (int i = 1; i <= size && num > 1; i++) { // 使用 45000 以内的质数对其进行分解
while (num % prime[i] == 0) {
map[i]++;
num /= prime[i];
}
}
if (num > 1) { // 如果剩余的数大于 1 ，那么这个数也一定是一个质数
prime[++size] = num;
map[size] = 1;
return 1;
}
return 0;
}
void init() { // 预处理出 45000 以内的所有质数
for (int i = 2; i <= 50000; i++) {
if (!notPrime[i])
prime[++size] = i;
for (int j = 1; j <= size && prime[j] * i <= 50000; j++) {
notPrime[prime[j] * i] = true;
if (i % prime[j] == 0)
break;
}
}
}
void solve() {
int tot = 0;
scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
if(b > a || d < c) {
printf("0\n");
return;
}
long long ans = 1;
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
memset(C, 0, sizeof(C));
memset(D, 0, sizeof(D));
//将a b c d 分别进行质因数分解，并统计新添加的质数的个数
tot += analyse(B, b);
tot += analyse(A, a);
tot += analyse(C, c);
tot += analyse(D, d);
for (int i = 1; i <= size; i++) {
bool flag = false;
if (D[i] == C[i] && A[i] == B[i])
ans *= (D[i] - B[i] + 1);
if (A[i] != B[i])//若A[i] != B[i] 那么结果的第i位一定与B[i]
if (D[i] != C[i]) // 判断是否可以取到 B[i]
flag = D[i] != B[i];
if (D[i] == C[i])
flag = B[i] > D[i];
if (C[i] != D[i])//若C[i] != D[i] 那么结果的第 i 位一定与D[i] 相等
if (A[i] != B[i])
flag = D[i] != B[i];
if (A[i] == B[i])
flag = D[i] < B[i];
if (flag) { //判断此组数据是否有解
printf("0\n");
return;
}
}
printf("%lld\n", ans);
size -= tot;//将预先处理处的大质数移去
}
int main() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
init(); //预处理 45000 以内的所有质数
int n;
scanf("%d", &n);
while (n--)
solve();
return 0;
}