洛谷1072:Hankson的趣味题

洛谷1072:Hankson的趣味题

题意:

  • 有:
    • \(gcd(x,a_0)=a_1\)
    • \(lcm(x,b_0)=b_1\)
  • 给定\(a_0,a_1,b_0,b_1\),问满足上述等式的\(x\)有多少个?

思路:

  • \(gcd(x,a_0)=a_1,gcd(\frac{x}{a_1},\frac{a_0}{a_1})=1\)。
  • \(lcm(x,b_0)=b_1,lcm(x,b_0)=\frac{x*b_0}{gcd(x,b_0)}\).
  • \(b_1=\frac{x*b_0}{gcd(x,b_0)},gcd(x,b_0)=\frac{x*b_0}{b_1}\).
  • \(gcd(\frac{b_1}{b_0},\frac{b_1}{x})=1\).
  • 所以我们得到两个式子:
    • \(gcd(\frac{x}{a_1},\frac{a_0}{a_1})=1\).
    • \(gcd(\frac{b_1}{x},\frac{b_1}{b_0})=1\).
  • 这时候我们发现,\(x\)是\(a_1\)的倍数,是\(b_1\)的因数,我们只需要\(\sqrt b_1\)枚举\(b_1\)的因子,之后判断符不符合条件即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a0, b0, a1, b1;

inline int gcd(int a, int b)
{
    if(b == 0) return a;
    return gcd(b, a%b);
}

inline ll lcm(ll a, ll b){
    return (a*b) / gcd(a,b);
}


inline bool check(int x){
    return gcd(x, a0) == a1 && lcm(x, b0) == b1;
}

inline void solve()
{
    //gcd(x, a0) = a1
    //lcm(x, b0) = b1
    //question: Number of x ?
    scanf("%d%d%d%d", &a0 , &a1, &b0, &b1);
    int ans = 0;
    for(int i = 1; i <= b1/i; i++)
    {
        if(b1 % i == 0)
        {
            ans += check(i) == true;
            if(i * i != b1) ans += check(b1/i) == true;
        }
    } printf("%d\n", ans);
}

int main()
{
    int T; scanf("%d", &T);
    while(T--) solve();
    return 0;
}
上一篇:python 地名地址解析(省、市、区县)


下一篇:alluxio 信息索引