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

Bismuth83 · 2025-01-15 10:01:11 · 题解

显然直接暴力不行，复杂度 O(n \times b_1)，会 TLE。

我们发现，x 肯定是 b_1 的因数，而除了平方数，因数都是成对的，所以我们在 1 和 \sqrt{b_1} 里枚举 x 和 \dfrac{b_1}{x} 是否满足条件就行了（因为 x 是 b_1 的因数，所以 \dfrac{b_1}{x} 一定是整数）。

但是 b_1 如果是 x 的平方的话，那 x 就与 \dfrac{b_1}{x} 相等了，会导致 x 被计数两遍。所以我们要特判一下 b_1 是 x^2 的情况，这时只需要判断一遍就可以了。

温馨提示：

• C++ 里求最大公因数的函数是 __gcd()，__gcd(x,y) 是求 x 和 y 的最大公因数。
• \operatorname{lcm}(x,y)= \dfrac{xy}{\gcd(x,y)}

#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;
}