我是新大一,今天看了一个很简单的比赛发现自己的数学知识不过关。这个代码我看不懂里面的数学方法,不知道为什么这样算出来的就是结果。代码能看懂只是不知道数学方法。求解释,谢谢啊?
其实很简单,就是先用l/x,得到范围最小值是x的多少倍,如果正好整除,那说明l就是x的倍数,否则将倍数加1,也就是k倍 。那么最小公约数是x的话,另一个最接近的整数就是(k+1)x了,但不如这个整数比范围最大之r大,那么就找不到满足要求的两个不同数了,输出-1,否则满足条件的两个整数就是kx和(k+1)x
求公约数的逆向来思考,先给定了一个数和范围,在范围内找出两个能够整除该数的数。先找到最小能够整除的倍数k,就算1个,k+1倍也能整除就2个了,若是k+1不符合,即使k符合也没用了,那就输出-1表示错误结束。
你可以将用例代入来理解,k=l/x; (k=1/5=0); if(l%x) 显然会执行k++,那么k=1,此时这个kx肯定是x的倍数并且kx>l,那么这时候你只需要判断(k+1)x是不是在<=r这个范围内,是就输出kx,(k+)x。否则在这个范围内就没有两个数的最大公约数=x。(其实你只要想清楚k不论何值kx一定是x的倍数,那么(k+1)*x当然肯定是,只需要判断在不在你给的范围中就行了)
没必要那么麻烦。。。。