专栏文章

题解：P1072 [NOIP2009 提高组] Hankson 的趣味题

BBismuth83
P1072题解参与者 4已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miqifhy5
此快照首次捕获于
2025/12/04 05:19
3 个月前
此快照最后确认于
2025/12/04 05:19
3 个月前
查看原文
显然直接暴力不行，复杂度 O(n×b1)O(n \times b_1)，会 TLE。
我们发现，xx 肯定是 b1b_1 的因数，而除了平方数，因数都是成对的，所以我们在 11 和 b1\sqrt{b_1} 里枚举 xx 和 b1x\dfrac{b_1}{x} 是否满足条件就行了（因为 xx 是 b1b_1 的因数，所以 b1x\dfrac{b_1}{x} 一定是整数）。
但是 b1b_1 如果是 xx 的平方的话，那 xx 就与 b1x\dfrac{b_1}{x} 相等了，会导致 xx 被计数两遍。所以我们要特判一下 b1b_1 是 x2x^2 的情况，这时只需要判断一遍就可以了。
温馨提示：
  • C++ 里求最大公因数的函数是 __gcd()，__gcd(x,y) 是求 xx 和 yy 的最大公因数。
  • lcm⁡(x,y)=xygcd⁡(x,y)\operatorname{lcm}(x,y)= \dfrac{xy}{\gcd(x,y)}
CPP
#include<bits/stdc++.h>
using namespace std;
int T;
int main(){
	cin>>T;
	for(int o=1;o<=T;o++){
		int ans=0;
		int a0,a1,b0,b1;
		cin>>a0>>a1>>b0>>b1;
		int qq=(int)sqrt(b1);
		for(int i=1;i<=qq;i++){
//注意 if 的顺序
			if(b1%i==0&&b1/i==i){
                //注意：求最小公倍数时，先除后乘，防止溢出。
				if(__gcd(i,a0)==a1&&i/__gcd(i,b0)*b0==b1) ans++;
				break;
			}
			else if(b1%i==0){
				if(__gcd(i,a0)==a1&&i/__gcd(i,b0)*b0==b1){
					ans++;
				}
				if(__gcd(b1/i,a0)==a1&&(b1/i)/__gcd(b1/i,b0)*b0==b1){
					ans++;
				}
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...