题解 P1072 【Hankson 的趣味题】
Zesty_Fox
2020-01-30 14:27:43
[原题链接](https://www.luogu.com.cn/problem/P1072)
嗯...~~通过标签~~我们易得知,这是一道数学题(废话)
其中,题目给了这两个条件:
$gcd(x,a_0)=a_1,lcm(x,b_0)=b_1$
所以,根据 $gcd$ 与 $lcm$ 的性质,我们可以得到如下结论:
$a_1|x,x|b_1$ , ${x} \over a_1$ 与 $a_0 \over a_1$ 互质, $b_1 \over x$ 与 $b_1 \over b_0$ 互质。
(请自行思考原因)
有了这个结论,接下来的枚举就十分简单了。直接枚举 $b_1$ 所有的因数,然后判断、累加答案即可。
代码时间:
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int ans,n,a0,a1,b0,b1;
//gcd(x/a1,a0/a1)=1,gcd(b1/x,b1/b0)=1
int gcd(int x,int y){
return x==0?y:gcd(y%x,x);
}
int main(){
cin>>n;
while(n--){
ans=0;
scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
int i=a0/a1,j=b1/b0;
for(int u=1;u*u<=b1;u++){
if(b1%u==0){
int v=b1/u;
if(u!=v){
if(u%a1==0&&gcd(u/a1,i)==1&&b1%u==0&&gcd(b1/u,j)==1) ans++;
if(v%a1==0&&gcd(v/a1,i)==1&&b1%v==0&&gcd(b1/v,j)==1) ans++;
}
else{//注意此处,有可能枚举的u=v,并且两者都满足条件,就重复累加了ans,所以需特殊判断
if(u%a1==0&&gcd(u/a1,i)==1&&b1%u==0&&gcd(b1/u,j)==1) ans++;
}
}
}
cout<<ans<<endl;
}
return 0;
}
```
蒟蒻第一次写博客,请大佬多多指教!