题解 009 题目 P1072

array2022 · 2025-01-18 16:02:18 · 题解

题目分析

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

部分分代码

#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 的特殊情况。

通过代码

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