题解 009 题目 P1072

题目分析

看到题目后可以先考虑暴力枚举，枚举 $1$ 到 $b_1$ 之间的数。时间复杂度 $O(nb_1)$ 。

部分分代码

CPP

#include<bits/stdc++.h>
using namespace std;
int n;
int gcd(int a,int b){
	return __gcd(a,b); // 内置函数。 
}
int lcm(int a,int b){
	return a/gcd(a,b)*b; // 防止超过 int 范围。 
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	while (n--){
		int a0,a1,b0,b1,ans=0;
		cin>>a0>>a1>>b0>>b1;
		for (int i=1;i<=b1;i++){
			if (gcd(i,a0)==a1&&lcm(i,b0)==b1) ans++;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

优化

由于有 $\operatorname{lcm}(x,b_0)=b_1$ ，肯定有 $x\mid b_1$ ，可以由此减少枚举次数。枚举 $b_1$ 的 $1$ 到 $\sqrt {b_1}$ 的所有约数（设为 $y$ ），那么另一个约数就是 $\dfrac{b_1}{y}$ ，这样就可以减小运行时间。时间复杂度 $O(n\sqrt{b_1})$ 。这个技巧在其他题目中也有应用。
注意上述枚举的过程中有 $y^2=b_1$ 的特殊情况。

通过代码

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int gcd(int a,int b){
	return __gcd(a,b); // 内置函数。 
}
int lcm(int a,int b){
	return a/gcd(a,b)*b; // 防止超过 int 范围。 
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	while (n--){
		int a0,a1,b0,b1,ans=0;
		cin>>a0>>a1>>b0>>b1;
		for (int i=1;i<=b1/i;i++){
			if (b1%i!=0) continue; // 枚举约数。
			if (gcd(i,a0)==a1&&lcm(i,b0)==b1) ans++;
			if (b1!=i*i){ // 注意排除特殊情况。
				if (gcd(b1/i,a0)==a1&&lcm(b1/i,b0)==b1) ans++;
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

题解 009 题目 P1072

文章操作

题目分析

部分分代码

优化

通过代码

相关推荐

评论

题解 009 题目 P1072