原题题号：1448

• 题目描述

任何一个有理数都可以表示成M/N的形式（M,N均为正整数）。例如1/2,2/4,3/6都是等值的有理数。给定若干有理数，等值有理数的值只能算一个，问这些有理数含有多少个值，并按从小到大输出各值及该值的有理数个数。

• 输入

第一行是整数n,表示随后有n组测试数据（n不超过10）。
每一组测试数据的第一行是一个整数m(m<=100000)，随后有m行，每一行都是A/B的形式, 1<=A,B<=1000000000

• 输出

于每一组测试数据，输出要求如下，第一行输出有理数值的个数p，随后的p行按从小到大的次序每一行输出一个A/B形式的值及其对应的有理数个数，用空格分开，要求A/B是最简分数。

• 样例输入

2
2
1/3
1/4
4
1/1
1/2
7/14
7/7

• 样例输出

2
1/4 1
1/3 1
2
1/2 2
1/1 2
首先化简分数需要计算分子分母的GCD，随后分子分母除以GCD结果即可。每个分数可以通过计算浮点数来直接比较大小、计算个数。此题难度不大，但合理使用STL可以大大减少代码量。
若使用手打GCD则使用辗转相除法，代码如下：

void simple(int &m, int &n)
    {
        int mm = m,nn=n;
        while(mm>0)
        {
            int c = nn % mm;
            nn = mm;
            mm = c;
        }
        m /= nn;
        n /= nn;
    }

此处传参为传入地址，方便直接对分数化简。同时，我们还能使用内建的__gcd函数，进一步缩减代码，该函数位于bits/algo.h中。代码如下：

void simple(int &m, int &n)
        {
            int t=__gcd(m,n);
            m /= t;
            n /= t;
        }

对于数据的存储，我们需要分数的浮点值、分数本身表示（可以是字符串也可以是两个整形）和分数出现的次数，而且题目输出需要排序，综合考虑选用map与pair配合使用。代码如下：

map<pair<double, string>, int>data;

map中的pair为Key，int为Value，pair中的double存储分数大小，string存储分数本身的表示，因此还需要将化简后int/int的分数转化成string，使用to_string函数即可完成转换，而/的插入由于string的+本身重载了，因此直接相加即可。map中的int为存储该分数出现的次数。由于map本身是按照Key升序排列的，又因为pair的比较方法会先按照pair.first升序排列，因此不需要重载，直接存储就能满足我们的需求。代码如下：

scanf("%d/%d",&a,&b);
simple(a, b);
string t1=to_string(a),t2=to_string(b),ans;
ans=t1;
ans=ans+'/';
ans+=t2;
data[make_pair((double)a/b, ans)]++;

输出有理数个数则使用data.size()方法。代码如下：

printf("%d\n",data.size());
for(auto i=data.begin();i!=data.end();i++)
    printf("%s %d\n",i->first.second.c_str(),i->second);

完整代码如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
void simple(int &m, int &n)
{
    int mm = m,nn=n;
    while(mm>0)
    {
        int c = nn % mm;
        nn = mm;
        mm = c;
    }
    m /= nn;
    n /= nn;
}
int main()
{   
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        int a,b;
        map<pair<double, string>, int>data;
        while(n--)
        {
            scanf("%d/%d",&a,&b);
            simple(a, b);
            string t1=to_string(a),t2=to_string(b),ans;
            ans=t1;
            ans=ans+'/';
            ans+=t2;
            data[make_pair((double)a/b, ans)]++;
        }
        printf("%d\n",data.size());
        for(auto i=data.begin();i!=data.end();i++)
            printf("%s %d\n",i->first.second.c_str(),i->second);
    }
    //system("Pause");
    return 0;
}

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/20.html
最后修改时间：2020-02-09 12:20:14
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！