本文主要是介绍SGU 126. Boxes,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题面Codeforces. Programming competitions and contests, programming communityhttps://codeforces.com/problemsets/acmsguru/problem/99999/126大意:给出A,B(0<A+B<2^31),每次操作可以将其中一个数减去另一个数,并让另一个数乘2,即(A,B)->(2A,B-A),前提是B>=A
问最终使得A,B有一个为0的最少操作数,或判定无解
由于2A,B-A这个形式非常像辗转相减法中(A,B)->(A,B-A),只是A变成2A了,于是我们考虑一次操作后这个2A对gcd的影响,由于gcd(A,B)=gcd(A,B-A),所以gcd(2A,B-A)只能是gcd(A,B)或 2gcd(A,B)并且我们知道最终态为(A+B,0),gcd为A+B
于是可以判断有解的充要条件为:A+B=2^kgcd(A,,B) k为自然数
那么,判断有解后如何求出操作数呢?其实,操作数就为k,下面我们来证明这一点
首先,设d=gcd(A, B),则A=xd,B=yd,其中gcd(x, y)=1(为了方便,我们令x<=y)
代入A+B=2^kgcd(A,,B),得到xd+yd=2^k d,即x+y=2^k
若k=0,则x,y中一个为0,一个为1,即A,B中有一个为0,显然操作数为k=0
若k>0,则2^k为偶数,x,y奇偶性相同,可以证明x和y都是奇数(若都是偶数则不互质)
操作后变为(2xd,(y-x)d),其中2x,y-x都为偶数,则gcd必然变为原来的两倍,即2d
由A+B=2^k d可知,k次操作后即到达目标态,得证
具体实现非常简单
这篇关于SGU 126. Boxes的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!