欢迎来看 “片” （的简介）

由于-\(看片\)-生涯转瞬即逝，于是我选择对“\(片\)”进行一定的总结：

相信你一定看懂了

由于开始的时间有一点晚，就姑且认为我以后会慢慢补充吧......

\(P7161\) [\(COCI2020\) \(-\) \(2021\)#\(2\)] \(Euklid\)

解：数学

\(GCD(a,b)=g\)
\(\implies a=g\times k1,b=g\times k2\)
\(R(a,b)=h\)
\(\implies\) \(a=h,b∈[h^k,2\times h^k)\)
\(\implies\) \(gk1=h,gk2∈[h^k,2\times h^k)\)
\(∵\) \(R(a,b)=R(gk1,gk2)\implies R(\lfloor \frac{k1}{k2} \rfloor,gk2)\) \(!!重点!!\)
\(\implies\) \(k1/k2=h,gk2∈[h^k,2\times h^k)\)
\(\implies\) \(k1/k2=h,k2∈[\lfloor \frac{h^k}{g} \rfloor,\lfloor 2 \times \frac {h^k}{g} \rfloor)\)
\(\implies\) \(k2∈[\lfloor \frac{h^k}{g} \rfloor,\lfloor 2 \times \frac {h^k}{g} \rfloor),k1=h \times k2\)

更具体的，k2直接去 $ \lceil \frac{h^k}{g} \rceil$, \(k1\) 要保证自己与 \(k2\) 互质，所以 \(k2\) 取 \(k1\times h+1\)
好吧，实际上这一系列上下取整让我感到非常不安，不过你可以自行检验一下