Euklid

Euklid

题意：

定义一个函数如下：
$$R(a,b)=\{\begin{array}{l}R(b,a)ifa<b\\ R(\lfloor \frac{a}{b}\rfloor ,b)ifa>=b>1\\ aifa>=b=1\end{array}$$
现在给你两个数g，h，分别代表gcd(a,b)=g,R(a,b)=h，现在要求你构造出a和b，输出a和b

Solution：

假设x，y为答案
$$\begin{gathered} 因为gcd(x,y)=g，所以我们假设x=ag,y=bg(在推导过程中默认b>a)，由最大公因数性质可知gcd(a,b)=1 \\ \{\begin{array}{l}gcd(a,b)=1\\ R(ag,bg)=h\end{array} \\ 换种写法 \\ \{\begin{array}{l}gcd(a,b)=1\\ R(\lfloor \frac{b}{a}\rfloor ,ag)=h\end{array} \end{gathered}$$
因为要得到R(x,y)=h，所以递归到底后肯定会出现R(h,1)
我们倒着推上去，保持左边的h不变
$$R(h,1)=R(h,[h^2,2h^2))=R(h,[h^3,2h^3))=...=R(h,[h^i,2h^i))$$
所以$ag\in [h^i,2h^i)$，因此我们只要先找出大于g的$h^i$，再保证其能整除g,即$x=h^i+(g-h^i\%g)$，这样就能保证x整除g
对于$\lfloor \frac{b}{a}\rfloor =h$，通过带余除法的性质可知$b=ah+[0,a)$，对于这个可以枚举去求。也可以发现这个结果$b=ah+1$能满足$gcd(a,b)=1$
证明：
$$\begin{gathered} gcd(a,b) \\ =gcd(a,ah+1) \\ =gcd(ah+1,a) \\ =gcd(a,1) \\ =gcd(1,0) \end{gathered}$$
所以最后的结果就是
$$\begin{gathered} x=ag=h^i+(g-h^i\%g) \\ y=bg=\frac{x}{g}\ast (\frac{xh}{g}+1) \end{gathered}$$

代码

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;

int t;
ll g,h;
int main()
{
   
    scanf("%d",&t);
    while(t--)
    {
   
        scanf("%lld%lld",&g,&h);
        ll q=1;
        while(q<=g)q=q*h;
        if(q%g)q=q+(g-q%g);
        ll a=q/g;
        ll b=a*h+1;
        a=a*g;
        b=b*g;
        printf("%lld %lld\n",a,b);
    }
    return 0;
}