[COCI2020/2021]Euklid

· · 题解

壹、题目描述 ¶

定义函数

R(a,b)= \begin{cases} R(b,a) &a<b \\ R(\lfloor{a\over b}\rfloor,b)&a\ge b>1 \\ a&b=1 \end{cases}

给定 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.

根据辗转相除法，我们有

\gcd(a,b)=g \Rightarrow gcd(h\times b^j+r,b)=\gcd(r,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，由于我们有

h^k\le gi<2h^k \Rightarrow {h^k\over g}\le i<{2h^k\over g}

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

{h^k\over g}+1<{2h^k\over g} \Rightarrow g<h^k

只需要找到这个 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;
}