给定 $g,h$，请找到 $a,b$ 使得 $\gcd(a,b)=g∧R(a,b)=h$. 保证 $g,h\le 200000$，可以证明，存在 $a,b\le 10^{18}$ 的解。

贰、题解 ¶

显然一道构造题，但是挺难想到。下面我们不妨假设 $a\ge b$.

首先想到的就是去考察 $R$ 的性质，如果你打表，你会发现......不，你什么都发现不了。

但是我们可以利用人类智慧，首先一定有 $R(h,h^k)=h$，更一般地，有 $R(h,h^k+r)=h$，我们只需要保证 $r<h^k$ 即可。

也即，有 $R(h,x)=h\Big(x\in [h^k,2h^k)\Big)$，如果我们不考虑 $\gcd$ 的限制，那么我们可以直接构造 $a=h^k,b=h$，但是像这样由一边除到尽头，我们始终需要强制让一边为 $h$，如 $b=h$，而此时我们是万般不能让 $\gcd(a,b)=g$ 的（除了可能存在的一些特殊情况）。所以，这种 “一边除到底” 好是好，但是不能满足所有条件。

但是我们可以考虑，当 $a/b$ 完之后，得到 $a'=h$，然后我们面对的是 $R(a',b)=R(h,b)$，然后用 $h$ 将 $b$ 除成 $1$，这个时候，$a=h\times b^j+r(r<b^j)$，且 $b\in[h^k,2h^k)$，并且得构造出 $\gcd(a,b)=g$.

根据辗转相除法，我们有

如果设 $b=gh$，考虑最简单的情况，$r=g∧j=1\Rightarrow a=h^2g+g=g(h^2+1)$，我们一定能够保证 $\gcd(h,h^2+1)=1$，这样似乎合法？

然后，你会发现你错了，举个栗子：当 $g=2,h=3$ 时，我们可以构造出 $a=20,b=6$，但是 $R(20,6)=2$，那么问题出在哪里？我们还有个前提条件是 $gh\in [h^k,2h^k)\Rightarrow g\in[h^{k-1},2h^{k-1})$，得保证这个，我们才能构造出正确的答案。

也就是说，如果 $g$ 给得不够好，就没有答案咯？那为什么题目 “可以证明” 存在 $a,b\le 10^{18}$？事实上，$b=gh$ 只是我猜测的其中一种情况，$b$ 不一定一定就是 $gh$，我们可以记 $b=gi$，保证 $b=gi\in [h^k,2h^k)$ 即可，即，$g\in\left[{h^k\over i},{2h^k\over i}\right)$ 即可。

至于如何找到这个 $i$，由于我们有

因为这个 $i$ 是个整数，我们只需要找到一个 $k$，满足区间 $\left[{h^k\over g},{2h^k\over g}\right)$ 包含至少一个整数即可，一个一定满足条件的不等式是

只需要找到这个 $k$ 就可以了，取 $i=\left\lceil{h^k\over g}\right\rceil$，而 $a=h\times b+g$.

但是值得注意的是，直接取 $i=\left\lceil{h^k\over g}\right\rceil$ 的同时，我们一定有 $i>1$，因为 $g<h^k$，但是至于为什么必须保证 $i>1$ 呢？因为我们的 $a=h\times b^j+r(r<b^j)$，在此我们取 $j=1$，则需保证 $r=g<b=gi$，显然，当 $i=1$ 时不等式不成立，但是我们取上取整保证了 $i>1$.

总复杂度 $\mathcal O(T\log_hg)$.

题解过于简单，直接给出构造方法：

$$b=g\left\lceil{h^K\over g}\right\rceil,a=hb+g\quad(g<h^K) $$

我只能说，这个构造方法没有时间还真想不到，或许只有 $\sf SYDevil$ 和 $\sf OID$ 可以直接出吧？

叁、参考代码 ¶

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;

// #define NDEBUG
#include<cassert>

namespace Elaina{
    #define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
    #define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
    #define fi first
    #define se second
    #define mp(a, b) make_pair(a, b)
    #define Endl putchar('\n')
    #define mmset(a, b) memset(a, b, sizeof a)
    // #define int long long
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    template<class T>inline T fab(T x){ return x<0? -x: x; }
    template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
    template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
    template<class T>inline T readin(T x){
        x=0; int f=0; char c;
        while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
        for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
        return f? -x: x;
    }
    template<class T>inline void writc(T x, char s='\n'){
        static int fwri_sta[1005], fwri_ed=0;
        if(x<0) putchar('-'), x=-x;
        do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
        while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
        putchar(s);
    }
}
using namespace Elaina;

ull R(ull a, ull b){
    if(a<b) return R(b, a);
    if(b==1) return a;
    return R(a/b, b);
}
ull gcd(ull a, ull b){ return b? gcd(b, a%b): a; }

ull g, h, k, tmp, i, a, b;

signed main(){
    freopen("euklid.in", "r", stdin);
    freopen("euklid.out", "w", stdout);
    rep(_, 1, readin(1)){
        g=readin(1llu), h=readin(1llu);
        tmp=1, k=0;
        while(g>=tmp) ++k, tmp*=h;
        // When x,y are integers the equation ceil(x/y)=(x+y-1)/y is established
        i=(tmp+g-1)/g, b=g*i, a=h*b+g;
        writc(a, ' '), writc(b);
    }
    return 0;
}