105 lines
3.6 KiB
C++
105 lines
3.6 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 50010;
|
||
typedef long long LL;
|
||
|
||
struct Node {
|
||
int prime; // 质数因子
|
||
int count; // 个数
|
||
} f[10]; // 一维：哪个质数因子，二维：有几个 f:因子
|
||
// 根据经验， primes[]={2,3,5,7,11,13,17,19,23}足够分解INT_MAX,共9个就够了
|
||
int fl; // 配合数组使用的游标
|
||
|
||
int d[1610], dl; // 约数数组,约数数组游标 d:约数
|
||
// 根据经验INT_MAX中约数个数最多的是1600个,开1610足够。
|
||
|
||
// 欧拉筛
|
||
int primes[N], cnt; // primes[]存储所有素数
|
||
bool st[N]; // st[x]存储x是否被筛掉
|
||
void get_primes(int n) {
|
||
memset(st, 0, sizeof st);
|
||
cnt = 0;
|
||
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;
|
||
}
|
||
}
|
||
}
|
||
|
||
// 最大公约数，辗转相除法
|
||
int gcd(int a, int b) {
|
||
if (b == 0) return a;
|
||
return gcd(b, a % b);
|
||
}
|
||
|
||
// 最小公倍数
|
||
int lcm(int a, int b) {
|
||
return b / gcd(a, b) * a; // 注意顺序，防止乘法爆int
|
||
}
|
||
|
||
/**
|
||
功能：根据分解完成的质数因子数组 获取 所有约数
|
||
u：走到已经求出的质数因子数组f面前，现在是第u个
|
||
p: 已经拼接完成的的约数，初始值是1,是0的话没法通过质数因子相乘得到结果，base=1
|
||
*/
|
||
void dfs(int u, int p) {
|
||
if (u == fl) { // 如果所有质数因子遍历完成 0~fl-1是所有质因子的下标
|
||
d[dl++] = p; // 约数又多了一个
|
||
return;
|
||
}
|
||
|
||
// 枚举当前质数因子f[u]使用几个,最少是0个，最多是f[u].count个
|
||
for (int i = 0; i <= f[u].count; i++) {
|
||
dfs(u + 1, p);
|
||
p *= f[u].prime; // 这两句话用的太漂亮了，完美的模拟了要0个，要1个，要2个...牛B plus!
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
get_primes(50000); // 求小的质数因子，sqrt(INT_MAX)<50000,开50000很保险
|
||
|
||
int n;
|
||
cin >> n;
|
||
while (n--) {
|
||
/*
|
||
读入四个数字
|
||
x 和 a0 的最大公约数是 a1
|
||
x 和 b0 的最小公倍数是 b1
|
||
*/
|
||
int a0, a1, b0, b1;
|
||
cin >> a0 >> a1 >> b0 >> b1;
|
||
|
||
fl = 0; // 多组数据，每次注意清零
|
||
int t = b1; // 拷贝出来，一直除到没有为止
|
||
|
||
// 枚举b1的每个质数小因子
|
||
for (int i = 0; primes[i] <= t / primes[i]; i++) {
|
||
int p = primes[i];
|
||
if (t % p == 0) {
|
||
int s = 0;
|
||
while (t % p == 0) t /= p, s++;
|
||
f[fl++] = {p, s}; // 记录小质数因子和个数
|
||
}
|
||
}
|
||
|
||
// 如果存在大的质因子，那么最多只有一个，比如2*7=14中的7,此时t=7
|
||
// 也可能b1本身就是一个质数，比如131,那么此时t=131
|
||
if (t > 1) f[fl++] = {t, 1}; // 记录到质数数组中
|
||
|
||
// 现在求出的是b1的所有质数因数，题目要求的是约数,利用dfs通过质数因子获取所有约数
|
||
dl = 0; // 多组测试数据，也清一下零吧！
|
||
dfs(0, 1); // 一次dfs，将质数因子数组 转换 约数数组,p的默认值是1
|
||
|
||
int res = 0; // 答案数量
|
||
for (int i = 0; i < dl; i++) { // 枚举所有约数
|
||
int x = d[i]; // 判断是不是符合题意
|
||
if (gcd(a0, x) == a1 && lcm(b0, x) == b1) res++;
|
||
}
|
||
// 输出结果
|
||
printf("%d\n", res);
|
||
}
|
||
|
||
return 0;
|
||
} |