「NOIP 2009」Hankson 的趣味题

传送门

problem

给定 a 0 , a 1 , b 0 , b 1 a_0,a_1,b_0,b_1 a0​,a1​,b0​,b1​，求满足下列条件的 x x x 的数量：

• gcd ⁡ ( x , a 0 ) = a 1 \gcd(x,a_0)=a_1 gcd(x,a0​)=a1​。
• l c m ( x , b 0 ) = b 1 \mathrm{lcm}(x,b_0)=b_1 lcm(x,b0​)=b1​。

数据范围： 1 ≤ a 0 , a 1 , b 0 , b 1 ≤ 2 × 1 0 9 1\le a_0,a_1,b_0,b_1\le2\times 10^9 1≤a0​,a1​,b0​,b1​≤2×109， T ≤ 2000 T\le2000 T≤2000，其中 T T T 是数据组数。

solution

这道题不难，主要就是 gcd ⁡ \gcd gcd 的一个小性质： gcd ⁡ ( x , y ) = k ⟹ gcd ⁡ ( x k , y k ) = 1 \gcd(x,y)=k\Longrightarrow \gcd(\frac x k,\frac y k)=1 gcd(x,y)=k⟹gcd(kx​,ky​)=1。

那么第一个式子就是 gcd ⁡ ( x a 1 , a 0 a 1 ) = 1 \gcd(\frac x{a_1},\frac{a_0}{a_1})=1 gcd(a1​x​,a1​a0​​)=1。

第二个式子，稍微化简一下可得：

x b 0 gcd ⁡ ( x , b 0 ) = b 1 gcd ⁡ ( x , b 0 ) = x b 0 b 1 gcd ⁡ ( b 1 b 0 , b 1 x ) = 1 \begin{aligned} \frac{xb_0}{\gcd(x,b_0)}&=b_1\\ \gcd(x,b_0)&=\frac{xb_0}{b_1}\\ \gcd(\frac{b_1}{b_0},\frac{b_1}{x})&=1 \end{aligned} gcd(x,b0​)xb0​​gcd(x,b0​)gcd(b0​b1​​,xb1​​)​=b1​=b1​xb0​​=1​

由于 x x x 是 b 1 b_1 b1​ 的因数，我们就可以 O ( b 1 ) O(\sqrt{b_1}) O(b1​

​) 枚举因数来解决了。

时间复杂度 O ( T b 1 ) O(T\sqrt{b_1}) O(Tb1​

​)。

code

#include<bits/stdc++.h>
using namespace std;
int T,a0,a1,b0,b1;
bool check(int x){
	if(x%a1)  return false;
	if(__gcd(b1/b0,b1/x)!=1)  return false;
	if(__gcd(x/a1,a0/a1)!=1)  return false;
	return true;
}
int main(){
	scanf("%d",&T);
	while(T--){
		int ans=0;
		scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
		for(int i=1;i*i<=b1;++i){
			if(b1%i==0){
				ans+=check(i);
				if(i*i!=b1)  ans+=check(b1/i);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}