Hankson 的趣味题

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1089 字

多组数据，每组给定a0,a1,b0,b1，求

一本通
例

正文

/*
原题：T1626「一本通 6.3 例 2」Hankson 的趣味题
题意：多组数据，每组给定 a0,a1,b0,b1，求满足 gcd(a0,x)=a1 且 lcm(b0,x)=b1 的正整数 x 的个数。
思路：由整除性先剪枝（a0%a1!=0 或 b1%b0!=0 直接为 0）；否则枚举 b1 的所有约数 x，逐个校验两条件。
复杂度：时间 O(n·√b1) / 空间 O(1)
易错点：lcm 计算用 b0*x/gcd，注意平方因子约数不要重复计数；需保证 a1|x。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b){
    return b?gcd(b, a%b):a;
}
// 检查 x 是否满足两个条件
bool ok(ll a0, ll a1, ll b0, ll b1, ll x){
    if(x%a1!=0) return false;
    if(gcd(a0, x)!=a1) return false;
    ll g=gcd(b0, x);
    if((b0/g)*x!=b1) return false;
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    while(n--){
        ll a0, a1, b0, b1;
        cin>>a0>>a1>>b0>>b1;
        if(a0%a1!=0 || b1%b0!=0){
            cout<<"0\n";
            continue;
        }
        ll ans=0;
        for(ll i=1;i*i<=b1;i++){
            if(b1%i!=0) continue;
            if(ok(a0, a1, b0, b1, i)) ans++;
            if(i!=b1/i){
                if(ok(a0, a1, b0, b1, b1/i)) ans++;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

Hankson 的趣味题

正文

一本通·提高篇的其它内容