题意:
在一个无穷大的棋盘上,有一只Magic Horse,它每次能跳一个a×b大小的位置。输入a,b;问Magic Horse能否去棋盘的任何一个位置
思路:
此题不能枚举,只能通过观察和理论上的证明。这里直接给出结论(证明略):若a,b同时满足以下两个条件,则能;否则不能;
①a+b是奇数,即a,b奇偶性不同
②a,b互质,即gcd(a,b)=1
2024-03-23 13:49:28
在一个无穷大的棋盘上,有一只Magic Horse,它每次能跳一个a×b大小的位置。输入a,b;问Magic Horse能否去棋盘的任何一个位置
此题不能枚举,只能通过观察和理论上的证明。这里直接给出结论(证明略):若a,b同时满足以下两个条件,则能;否则不能;
①a+b是奇数,即a,b奇偶性不同
②a,b互质,即gcd(a,b)=1
下一篇:[机房测试] 出租车