Ta có số "k-phân" được viết dưới định dạng:

~d.eb~

Với:

• ~d~ là phần nguyên.
• ~e~ là phần "k-phân" không vô hạn tuần hoàn.
• ~b~ là phần "k-phân" vô hạn tuần hoàn.

Ta sẽ biến đổi từng phần từ dạng "k-phân" về dạng phân số thập phân rồi cộng các phân số lại để được kết quả cuối cùng, cách biến đổi từng phần như sau:

Biến đổi ~d~ từ số "k-phân" về dạng phân số thập phân

Xem ~d~ là dãy số gồm ~D~ chữ số: ~d_1d_2d_3\dots d_D~, công thức chuyển đổi về dạng thập phân là:

~d = \sum_{i=1}^D d_ik^{D-i}~

Biến đổi ~0.e~ từ số "k-phân" về dạng phân số thập phân

Xem ~e~ là dãy số gồm ~E~ chữ số: ~e_1e_2e_3\dots e_E~, công thức chuyển đổi ~0.e~ về dạng thập phân là:

~0.e =\frac{e}{k^E}=\frac{1}{k^E}\sum_{i=1}^E e_ik^{E-i}~

Biến đổi ~0.b~ về dạng phân số thập phân

Lưu ý, ~b~ là một dãy số có vô hạn chữ số tuần hoàn. Ta gọi ~B~ là độ dài của một dãy số tiền tố bất kỳ sao cho:

~b_i=b_{i \texttt{ mod } B}~

Ta gọi:

~T = \sum_{i=1}^B b_ik^{B-i} ~

Ta có công thức chuyển đổi từ ~0.b~ thành dạng phân số thập phân như sau:

~0.b \times k^B = T.b~

~\Rightarrow T.b - 0.b=0.b\times (k^B-1)~

~\Rightarrow T=0.b\times (k^B-1)~

~\Rightarrow 0.b = \frac{T}{k^B-1} = \frac{1}{k^B-1}\sum_{i=1}^B b_ik^{B-i}~

Cách cộng các phần lại thành kết quả cuối cùng

Ta có số "k-phân" được viết dưới định dạng:

~d.eb~

Từ định dạng trên ta có thể viết lại thành tổng như sau:

~d.eb=d+0.e+\frac{0.b}{k^E}~

~=\sum_{i=1}^D d_ik^{D-i} + \frac{1}{k^E}\sum_{i=1}^E e_ik^{E-i} + \frac{1}{k^E(k^B-1)}\sum_{i=1}^B b_ik^{B-i}~

Code mẫu

/*
Author : DeMen100ns (a.k.a Vo Khac Trieu)
School : VNU-HCM High school for the Gifted
fuck you adhoc
*/

#include <bits/stdc++.h>
#define endl '\n'

#define int long long

using namespace std;

const int N = 2e5 + 5;
const long long INF = 1e18 + 7;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;

int f(int k, string n){
    int ans = 0;

    for(char c : n){
        ans *= k;
        ans += (c - '0');
    }

    return ans;
}

pair<int, int> addfrac(pair<int, int> a, pair<int, int> b){
    int ansa = a.first * b.second + a.second * b.first;
    int ansb = a.second * b.second;

    int g = __gcd(ansa, ansb);
    ansa /= g; ansb /= g;
    return {ansa, ansb};
}

pair<pair<int, int>, int> fd(int k, string A){
    int pos = -1;
    for(int i = 0; i < (int)A.size(); ++i){
        if (A[i] == '.') pos = i;
    }
    int ansa = 0, ansb = 0, ct = 0;
    int prod = 1, pw = 1;
    for(int i = pos - 1; i >= 0; --i){
        ansa += prod * (A[i] - '0');
        prod *= k;
    }

    for(int i = pos + 1; i < (int)A.size(); ++i){
        ansb *= k;
        ansb += (A[i] - '0');

        pw *= k;
        ++ct;
    }
    pair<int, int> p = addfrac({ansa, 1}, {ansb, pw});

    return {p, ct};
}

void solve()
{
    int k; string A, B; 
    cin >> k >> A >> B;

    int len = B.size();

    pair<pair<int, int>, int> st = fd(k, A);
    pair<int, int> p1 = st.first;
    int l = st.second;

    //calculate b
    int b = f(k, B);
    int pa = b;
    int tmp = 1;
    for(int i = 1; i <= len; ++i) tmp *= k;
    int pb = tmp - 1;
    for(int i = 1; i <= l; ++i) pb *= k;

    int g = __gcd(pa, pb);
    pa /= g; pb /= g;

    pair<int, int> p2 = {pa, pb};

    pair<int, int> pans = addfrac(p1, p2);
    cout << pans.first << " " << pans.second << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // freopen("codeforces.inp","r",stdin);
    // freopen("codeforces.out","w",stdout);

    int t = 1; cin >> t;
    while (t--)
    {
        solve();
    }
}