CF1720A 题解

__vector__ · 2022-08-19 12:39:37 · 题解

题外话

感觉这道题有点降智（应该只是对我来说），就写一篇题解记录一下。

做法

我们可以这样理解：分母乘上一个数 x ，就代表这个分数除以 x；分子乘上一个数 x，就代表这个分数乘 x。

我们先假设：

转化为：

然后计算得出：

这样我们就知道了，\frac{a}{b} 分子和分母各乘上多少，才能与 \frac{c}{d} 相等。

如果 x = 1，那么分子不需要作乘法，否则分子需要进行一次乘法。
同理，如果 y=1，那么分母不需要作乘法，否则分母需要进行一次乘法。

这样就结束了吗？没有。

分子可能为 0。

如果两个分数的分子中有一个为 0，那么只需要将另一个分数的分子乘上 0，就行了。

如果两个分数的分子都为 0，那么不需要处理。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    int t;
    ll gcd(ll a,ll b)
    {
        return !b?a:gcd(b,a%b);
    }
    ll lcm(ll a,ll b)
    {
        return a/gcd(a,b)*b;
    }
    void main()
    {
        scanf("%d",&t);
        while(t--)
        {
            ll a,b,c,d;
            scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
            if(a==0&&c!=0)
            {
                printf("1\n");
                continue;
            }
            else if(a!=0&&c==0)
            {
                printf("1\n");
                continue;
            }
            if(a==0&&c==0)
            {
                printf("0\n");
                continue;
            }
            a*=d;
            b*=c;
            ll _gcd=gcd(a,b);
            a/=_gcd;
            b/=_gcd;
            int ans=0;
            if(b>1)ans++;
            if(a>1)ans++;
            printf("%d\n",ans);
        }
    }
}
int main()
{
    Main::main();
    return 0;
}