唯一分解定理
Hanks 博士是 BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。
今天在课堂上，老师讲解了如何求两个正整数 c_1c 1 和 c_2c 2
的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 a_0,a_1,b_0,b_1a 0 ,a 1 ,b 0 ,b 1 ，设某未知正整数x满足：xx 和 a_0a 0 的最大公约数是 a_1a 1
；xx 和 b_0b 0 的最小公倍数是 b_1b 1 。
Hankson 的“逆问题”就是求出满足条件的正整数 xx 。但稍加思索之后，他发现这样的 xx 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 xx 的个数。请你帮助他编程求解这个问题。
输入格式
第一行为一个正整数 nn ，表示有 nn 组输入数据。接下来的 nn 行每行一组输入数据，为四个正整数 a_0a
0 ，a_1a
1 ，b_0b
0 ，b_1b 1 ，每两个整数之间用一个空格隔开。输入数据保证 a_0a
0 能被 a_1a 1 整除，b_1b 1 能被 b_0b 整除。
输出格式
对于每组数据：若不存在这样的 xx ，请输出 00；
若存在这样的 xx ，请输出满足条件的 xx 的个数；
数据范围
对于 50%50% 的数据，保证有 1 \le a_01≤a
0
，b_1b
1
，b_0b
0
，b_1 \le 10000b
1
≤10000 且 n \le 100n≤100。
对于 100%100% 的数据，保证有 1 \le a_01≤a
0
，b_1b
1
，b_0b
0
，b_1 \le 2,000,000,000b
1
≤2,000,000,000 且 n \le 2000n≤2000。
样例说明
第一组输入数据，xx 可以是 99、1818、3636、7272、144144、288288，共有 66 个。
第二组输入数据，xx 可以是 4848、17761776，共有 22 个。
输出时每行末尾的多余空格，不影响答案正确性
样例输入复制
2
41 1 96 288
95 1 37 1776
样例输出复制
6
2
解题思路：将a,b,c,d分解质因数存起来，用map存，然后枚举每个质数的t次，利用两个数质因子指数最小值等于约数的质因子指数，两个数的质因子的最大值等于最小公倍数的质因子指数，就好了。这题小技巧，用map<int,node> first代表质因子，node代表结构体里面存a,b,c,d
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const int N=1000010;
struct node{
int a;
int b;
int c;
int d;
};
map<int,node>mp;
int prime[N],cnt;
bool st[N];
void getprime(int n)
{
for(int i=2;i<=N;i++)
{
if(!st[i])
prime[cnt++]=i;
for(int j=0;prime[j]<=N/i;j++)
{
st[i*prime[j]]=true;
if(i%prime[j]==0)
break;
}
}
}
int tt[5];
int main()
{
getprime(N);
int n;
cin>>n;
while(n--)
{
mp.clear();
int a,b,c,d;
cin>>a>>b>>c>>d;
tt[1]=a,tt[2]=b,tt[3]=c,tt[4]=d;
for(int idx=1;idx<=4;idx++)
{
int cc=tt[idx];
for(int i=0;i<cnt&&(ll)prime[i]*prime[i]<=cc;i++)
{
if(cc%prime[i]==0)
{
int cnt=0;
while(cc%prime[i]==0)
{
cc/=prime[i];
cnt++;
}
if(idx==1)
mp[prime[i]].a=cnt;
if(idx==2)
mp[prime[i]].b=cnt;
if(idx==3)
mp[prime[i]].c=cnt;
if(idx==4)
mp[prime[i]].d=cnt;
}
}
if(cc>=2) //判断素数的情况
{
if(idx==1)
mp[cc].a=1;
if(idx==2)
mp[cc].b=1;
if(idx==3)
mp[cc].c=1;
if(idx==4)
mp[cc].d=1;
}
}
long long res=1;
for(auto it:mp){
int cnt=0;
for(int j=0;j<=31;j++)
{
node t=it.second;
int a=t.a,b=t.b,c=t.c,d=t.d;
if(min(j,a)==b&&max(c,j)==d)
cnt++;
}
res = res * cnt;
}
cout<<res<<endl;
}
return 0;
}
