数论 | 同余 | 一中OJ_P1133【培训题】Hankson的趣味题

<font color=orange size=5>跳转到在线页面</font>

<font color=#3199DF > Description</font>

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的个数。请你帮助他编程求解这个问题。

<font color=#3199DF > Input</font>

第一行为一个正整数n,表示有n组输入数据。接下来的n行每行一组输入数据,为四个正整数a0,a1,b0,b1,每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除,b1能被b0整除。

<font color=#3199DF > Output</font>

共n行。每组输入数据的输出结果占一行,为一个整数。  对于每组数据:若不存在这样的x,请输出0;  若存在这样的x,请输出满足条件的x的个数;

<font color=#3199DF > Sample Input</font>

2
41 1 96 288
95 1 37 1776

<font color=#3199DF > Sample Output</font>

6
2

<font color=#3199DF > Hint</font>

对于50%的数据,保证有1≤a0,b1,b0,b1≤10000且n≤100。对于100%的数据,保证有1≤a0,b1,b0,b1≤2,000,000,000且n≤2000。

<font color=purple > 分析</font>

两个数的乘积等于这两个数的最大公约数与最小公倍数的乘积

——百度热心网友

首先由: 可知x是b1的一个因子且为a1倍数,因而从1到sqrt(b1)枚举每个整除b1的数字,若其是a1的整数倍,且满足上述二式则ans+1 暴力枚举在一中OJ上可以得90分…

100分解法还要推出更深的结论: 则: 进一步的我们有: 设置几个辅助变量: 考虑gcd(s/p,n)=1要满足s/p与n没有公共质因数,因此我们需要将s/p与n的公共质因数筛去,得到满足条件的数T,T是s/p的某个因数

又因为gcd(p,m)=1,而s/p=Tr(r为整数),那么p=s/(T*r),则gcd(s/(T*r),n)=1,利用刚才方法将两者的公共质因数筛去得到S,那么S的因数个数就是答案

<font color=green > Codes</font>

// hankson 趣味题 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a0,a1,b0,b1,ans;
LL gcd(LL a,LL b)
{
	if(a<b) swap(a,b);
	return b==0?a:gcd(b,a%b);
}
inline LL lcm(LL a,LL b)
{
	return a*b/gcd(a,b);
}
inline LL seprate(LL a,LL b)
{
	LL S=sqrt(b);
	for(LL i=2;i<=S;i++){
		if(b%i==0)
			while(a%i==0) a/=i;
		while(b%i==0) b/=i;
	}
	if(b!=1) while(a%b==0) a/=b;
	return a;
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("testin.txt","r",stdin);
	freopen("testout.txt","w",stdout);
	#endif
	int T;
	cin>>T;
	while(T--){
		cin>>a0>>a1>>b0>>b1;
		ans=0;
		LL m=a0/a1,n=b1/b0,s=b1/a1;
		LL tmp1=seprate(s,n);
		if(gcd(s/tmp1,m)!=1) cout<<0<<'\n';
		else{
			LL tmp2=seprate(tmp1,m);
			LL S=sqrt(tmp2);
			for(LL i=1;i<=S;i++)
				if(tmp2%i==0)
					ans+=(tmp2/i==i)?1:2;
			cout<<ans<<'\n';
		}
	}
	return 0;
}