题目

题目描述

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$的个数；

输入输出样例

输入样例

2
41 1 96 288
95 1 37 1776

输出样例

6
2

题解

因为$x$是$b_1$的约数，所以$x$的质因子一定也是$b_1$的质因子，所以我对于$b_1$的每个质因子$p$，我们可以计算$x$中有多少个$p$
假设$a_0,a_1,b_0,b_1,x$中分别有$m_{a_0},m_{a_1},m_{b_0},m_{b_1},m_x$个质因子$p$
由于$gcd(a_0,x)=b_0$，所以有$3$种情况：

若$m_{a_0}>m_{b_0}$，则$m_x=m_{b_0}$
若$m_{a_0}=m_{b_0}$，则$m_x\geqslant m_{b_0}$
若$m_{a_0}<m_{b_0}$，则$m_x$无解

同理，由于$lcm(a_1,x)=b_1$，所以有$3$种情况：

若$m_{a_1}<m_{b_1}$，则$m_x=m_{b_1}$
若$m_{a_1}=m_{b_1}$，则$m_x\leqslant m_{b_1}$
若$m_{a_1}>m_{b_1}$，则$m_x$无解

综合以上所有情况，我们可以得出共有$5$种情况：

若$m_{a_0}>m_{b_0},m_{a_1}<m_{b_1},m_{b_0}=m_{b_1}$，则$m_x=m_{b_0}=m_{b_1}$
若$m_{a_0}>m_{b_0},m_{a_1}=m_{b_1},m_{b_0}\leqslant m_{b_1}$，则$m_x=m_{b_0}$
若$m_{a_0}=m_{b_0},m_{a_1}<m_{b_1},m_{b_0}\leqslant m_{b_1}$，则$m_x=m_{b_1}$
若$m_{a_0}=m_{b_0},m_{a_1}=m_{b_1},m_{b_0}\leqslant m_{b_1}$，则$m_{b_0}\leqslant m_x\leqslant m_{b_1}$
若其他情况，则$m_x$均无解

我们将$m_x$的取法记为$sum_p$，则$x$的数量为$\prod\limits_{\text{质数}p|d}sum_p$
代码如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a0,a1,b0,b1,ans;
int gcd(int a,int b)
{
  return b==0?a:gcd(b,a%b);
}
long long lcm(int a,int b)
{
  return (long long)a*b/gcd(a,b);
}
int main()
{
  cin>>n;
  while(n--){
    ans=0;
    scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
    for(int i=1;i<=sqrt(b1);i++)
    if(b1%i==0){
          if(gcd(i,a0)==a1&&lcm(i,b0)==b1) ans++;
      if(i*i!=b1) if(gcd(b1/i,a0)==a1&&lcm(b1/i,b0)==b1) ans++;;
    }
    printf("%d\n",ans);
  }
}