题解 gcd 数论

题解P1482 Cantor表（升级版）

Posted by n0000000000o's Blog on April 17, 2018

本题其实就是一个化简题。。#

关键是乘了之后的约分，

然而小学数学告诉我们，约分只需要两步：

1.求出分母分子的最大公因数（最大公约数）

2.然后分母分子同时除以这个数。

可以用辗转相除法或更相减损法

在此送上代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d;
    char x;
    cin>>a>>x>>b >>c>>x>>d;//x防止“/”的输入
    a*=c;b*=d;
    //之后c和d就没用了
    c=a;d=b;
    //更相减损法
    while(c!=d)
    {
        if(c>d)
            c-=d;
        else
            d-=c;
    }
    
    int ww=d;//此时ww为最大公因数
    a/=ww;b/=ww;
    cout<<b<<" "<<a<<endl;//注意是先列再行
}