题目描述

Tang Keke is good at math. She knows how to simplify fractions very well. Even greater, she invented a simplifying method by herself!

The method is to choose some digits which appear in both the top and the bottom and erase them on both sides while keeping the fraction value unchanged. The digits are the same, so they can reduce each other. Sounds very logical, right?

The method may produce multiple simplified results and the one with the least top number is called the most simplified form. Keke prepared some fractions and is going to test if you can get the most simplified form.

Note that the chosen digits form a multiset, you can see the examples for more details.

大家都知道两个分数等价是什么概念，我们说a/b 和 p/q 等价当且仅当a/b=p/q。

通常我们约分是将分子分母同时约去一个相同的因数。但是这样太难了，于是小t对约分提出了新的定义。我们可以一次性从分子分母中同时划掉若干个相同的数字。比如， 123/233可以划掉一个数变成12/23， 也可以变成13/33，容易发现这样可能造成原来的分数跟当前的分数不等价。

现在小t想问你， 在此约分操作下a/b的最简分数是哪一个。最简分数是，与a/b等价的p/q中，p最小的那一个。比如

• 163/326→16/26→1/2，我们说1/2是163/326的最简分数

• 24/48的最简分数是24/48， 因为2/8≠24/48。

• 22222/22222的最简分数是2/2， 因为0/0不合法。

需要注意的是， 如果答案是007/233， 你需要输出的是7/233。可以理解为前导零会在约分的过程中自动消散。

输入格式

The first line contains an integer n(1≤n≤10), denoting the number of fractions.

Each of the next n lines contains two integer p,q(0<p,q<263), denoting the fraction p/q.

一行两个整数a,b， 分别表示分子和分母。

输出格式

For each fraction, output two integers x,y in one line, indicating the most simplified form of the corresponding fraction is x/y.

Notice: if there are some leading zeros after removal, you can ignore them and output the normal number. For example, if you get 007/123 finally, then you should output “7 123” instead of “007 123”.

一行两个整数p,q， 分别表示最简分数的分子和分母。

思路

$2^{63} == 9,223,372,036,854,775,808$, 其长度为19, 也就是说, 我们其实可以用二进制枚举每一种删除的情况, 删除情况合法是, 进行判断是否相等, 最终找到最小的分子答案

细节:

对于分子, 我们用二进制中的每一个0将分子进行了删除操作, 对于那些被删除的数, 我们记录在一个cnt数组中

对于分母, 同样一个数字我们可能在多个地方都有删除操作, 全部枚举不太现实, 于是从侧面出发: 分子和比例已经固定的情况下, 那么分母也是被固定的, 我们算出理想的分母, 然后再实际的分母上进行删除, 如果不能完成全部的删除操作, 则该方法不成立

删除完成后, 会进行一个相等的判断, 但是我们在进行分母的判断时, 是按照比例来计算的, 所以我们得在计算完分子之后, 判断分子是否是比例中分子的倍数. 因为相等分数之间的最简分数一定是相同的

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long LL;

LL a, b;
vector<int> x, y;
int cnt[10];

vector<int> get(LL x) {
    vector<int> ans;
    while (x) {
        ans.push_back(x % 10);
        x /= 10;
    }
    return ans;
}

LL check(LL st) {
    for (int & i : cnt) i = 0;

    LL fz = 0;
    for (int i = x.size() - 1; i >= 0; i -- )
        if (st >> i & 1) fz = fz * 10 + x[i];
        else cnt[x[i]] ++;

    if (!fz || fz % a != 0) return -1;

    LL fm = fz / a * b;
    for (int i : y)
        if (fm % 10 != i) cnt[i] --;
        else fm /= 10;

    if (fm) return -1;
    for (int i : cnt)
        if (i)
            return -1;
    return fz;
}

int main() {
    scanf("%lld%lld", &a, &b);
    x = get(a), y = get(b);
    LL fz = a, fm = b;
    LL t = __gcd(a, b);
    a /= t, b /= t;
    for (int i = 0; i < (1 << x.size()) - 1; i ++ ) {
        LL t = check(i);
        if (t != -1 && t < fz) fz = t, fm = t / a * b;
    }
    cout << fz << ' ' << fm << endl;
}