题解：UVA10814 Simplifying Fractions

xyx404 · 2025-06-30 13:59:04 · 题解

题意：

输入 n 行，每行一个分数，格式为 p / q（数字与字符中间有空格），你需要将分数简化到最简形式并按格式输出。
其中 1\le p,q \le 10^{30}。

思路：

我们知道，一个分数的最简形式可以通过将分子和分母同时除以它们的最大公因数来获得。

那么先不考虑数据范围，我们可以得到一个简单的代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int n;
LL p,q;
int main(){
    cin>>n;
    char k;
    while(n--){
        cin>>p>>k>>q;
        LL gcd=__gcd(p,q);
        cout<<p/gcd<<" / "<<q/gcd<<"\n";
    }
    return 0;
}

那么加上数据范围呢？我们可以请出神奇的 __int128，它表示的范围大约是 \pm{10^{38}}，实际范围是 -2^{127} \sim 2^{127} - 1，对于我们的数据范围最大只有 10^{30} 是足够的。

特别注意 __int128 不能直接用 cin 输入和 cout 输出。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
__int128 p,q;
int n;
__int128 read(){
    __int128 x=0;
    bool f=0;
    char c=getchar();
    while(!(c>='0'&&c<='9'))c=getchar(),f=!f;// 因为输入中间有空格，要去除！
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;// 本题保证输入为正数，所以直接返回
}
void write(__int128 x){
    if(x>0){// 本题保证 1<=p,q<=10^30 是正数，所以不考虑负数了
        write(x/10);
        cout<<int(x%10);
    }
    return;
}
int main(){
    cin>>n;
    char k;
    while(n--){
        p=read();
        cin>>k;// 中间的除号
        q=read();
        p=-p;q=-q;
        __int128 gcd=__gcd(p,q);
        write(p/gcd);cout<<" / ";write(q/gcd);cout<<"\n";
    }
    return 0;
}

AC 记录。