题解 | Hankson 的趣味题

题目大意

求出一个正整数 $x$ 满足 $\tt{gcd(x,a_0)=a_1}$ 且 $\tt{lcm(x,b_0)=b_1}$。

解题思路

首先想到的是直接枚举 $x$，如果满足要求则累加答案，因为 $x>b_1$ 一定不满足 $\tt{lcm(x,b_0)=b_1}$，所以 $x$ 从 $1$ 一直枚举到 $b1$。代码如下：

#include<iostream>
#include<math.h>
#define ll long long
using namespace std;
ll n,a0,a1,b0,b1,ans;
ll gcd(ll x,ll y){
	return (y==0?x:gcd(y,x%y));
}
ll lcm(ll x,ll y){
	return (x/gcd(x,y)*y);
}
int main(){
	cin>>n;
	while(n--){
		cin>>a0>>a1>>b0>>b1;
		ans=0;
		for(ll i=1;i<=b1;++i){
			if(gcd(i,a0)==a1&&lcm(i,b0)==b1)++ans;
		}
		cout<<ans<<endl;
	}
	return 0;
}

时间复杂度 $O(n\cdot b_1)$，只适用于 $50\%$ 的数据，需要再优化。

优化思路

因为 $\tt{lcm(x,b_0)=b_1}$ 的前提条件是 $x\mid b_1$，即 $x$ 是 $b_1$ 的因数，枚举 $b_1$ 的因数的时间复杂度是 $O(\sqrt{b_1})$，再判断是否满足 $\tt{gcd(x,a_0)=a_1}$ 和 $\tt{lcm(x,b_0)=b_1}$ 的条件即可，时间复杂度 $O(n\cdot\sqrt{b_1})$。

参考代码

#include<iostream>
#include<math.h>
#define ll long long
using namespace std;
ll n,a0,a1,b0,b1,ans;
ll gcd(ll x,ll y){
	return (y==0?x:gcd(y,x%y));
}
ll lcm(ll x,ll y){
	return (x/gcd(x,y)*y);
}
int main(){
	cin>>n;
	while(n--){
		cin>>a0>>a1>>b0>>b1;
		ans=0;
		for(ll i=1;i<=sqrt(b1);++i){
			if(b1%i==0){
				if(gcd(i,a0)==a1&&lcm(i,b0)==b1)++ans;
				int j=b1/i;
				if(i!=j){
					if(gcd(j,a0)==a1&&lcm(j,b0)==b1)++ans;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}