首先m，n不能有大于1的公约数，否则只能跳到公约数倍数的点，这个很好想。

为什么不能同是奇数呢？

我考虑了一下，可以如下证明：

马可以跳（m，n）或跳（n，m）因此能跳到的点应该属于（xm+yn，xn+ym）集合（x，y属于整数），而如果m，n奇偶性相同，那么xm+yn，xn+ym必然奇偶性相同。

因此无法跳到奇偶性不相同的点。

所以说可以遍历的充要条件，就向下面大牛说的：

m+n是奇数，并且互质

只要m+n是奇数，并且互质，就能遍历，判断奇数很简单，判断互质，只要用辗转相减法就不会超时。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

无语了，经典的数论题啊，数学不好怎么办啊？！考试的时候做到怎么办啊？！

！！！！！

？？？？？

跑到这来找题解。。。

对你无语了

(0,1)可以遍历

(0,3)不能遍历

但我觉的（3，5）也可以遍历

不知大牛们怎么觉得

将n*m的广义马对应1*n的广义马

第1种情况:若n,m有最大公约数p(p>1),则马只能跳到形似(p*s,p*t)的格子上,其他的格子都到达到不了.

第2种情况:若n+m是偶数,类似于1*n马的情况,马只能在同色的格子内跳动,不能遍历棋盘.

第3种情况:若n+m为奇数且n,m互质.不妨设n为奇数,那么m为偶数.因为1*n马的问题已经被彻底解决,所以很自然的想将n*m经过一系列变换转化成1*n马的问题.我们可以看到马的跳法本质上是4种(另4种可以看成是以下4种跳法反跳一步):

①(m,n) ②(m,-n) ③(n,m) ④(n,-m)

马经过跳p次①,q次②,r次③,s次④后

水平方向的位移为(p+q)*m+(r+s)*n 竖直方向的位移为(p-q)*n+(r-s)*m

为了利用1*n马的结论,解不定方程(p+q)*m+(r+s)*n=1.

∵n,m互质.∴该方程一定有解(p0,q0,r0,s0).

又∵m是偶数n是奇数.∴(p0+q0)是偶数,(r0+s0)是奇数.

∵(p0+q0)与(p0-q0)同奇偶,而(r0+s0)与(r0-s0)同奇偶.

∴(p0-q0)是偶数,(r0-s0)是奇数.

∴(p0-q0)*n+(r0-s0)*m是偶数.

也就是马通过一系列的跳动所得到的效果相当于1*len的马跳一步的效果(len=(p0-q0)*n+(r0-s0)*m).根据前面的结论,1*len的马可以遍历整个棋盘,所以当n+m为奇数且n,m互质时,n*m的马可以遍历整个棋盘

找了半天就找到这么多..可还是不太懂...

只要马能走到（1，0）就可以遍历整个棋盘。。。

只要能走到（1，0），意味着也可以走到（0，1），（-1，0），（0，-1）

用这4个坐标可以组合出任意其他坐标

提醒一下没过的，0 0 是n

但 0 ？ 或者 ？ 0 可是 y

啊啊啊啊啊啊，我的AC率

当N+M为奇数且N,M互质时可以遍历整个棋盘

经典.....................

其实想不明白楼下大牛的算法完全可以用深搜做，只要判断从第1个点出发，按照给定的方法能否走到其边上的点就可以了……我2种方法都写出来啦

^__^

最后一个点完全没有问题，只要在朴素的互质算法上减小范围就可以了

把结论说出来吧。

当N+M为奇数且N,M互质时可以遍历整个棋盘

8723 1034

和

78 87

为什么都是n呢？？看不懂

按odd(m+n)的两种情况讨论...

就是一很没意思的数学题.

... 难道不能改数据么？

要求改后并且rejudge

我是出题者。其实标程的算法是o(k)，也就是说每个数据是o(1)

快要出来了...大概就是能不能走出一步..

最后一个点有问题...

用了一个卑劣的手段...

不是我本意啊..