唯一分解定理

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;
	}