Problem Description
实验室的“猪猪”一开始在1号格子，开始向前走，每步一格，并且每走 k 步会在当前的格子上打上记号（开始时，1号格子也有记号）。由于这是死胡同，每当“猪猪”走到最左或者最右的格子时，它会改变方向。好奇的“猪猪”在想：如果我一直走，能否把所有格子都打上记号呢？
聪明的你一定知道答案！
Hint1：如果 n=6，k=2，位置变化为：1 -> 3 -> 5 -> 5 -> 3 -> 1 -> 3 -> 5 .... 显然，此时不能将所有格子打上标记。(如下图）
Input
每组数据一行，包含两个正整数 n 和 k。
（1 <= n <= 100000 , 1 <= k <= 100000）
Output
Sample Input
6 2 6 3
Sample Output
NO YES
Author
声明：由于再次提交时已经Out of Contest Time，所以自己的做法无法百分百保证正确。但是我和学长的答案算法随机测了10组相同的数据组，结果一致，应该八九不离十了吧~【机智的我，从学长那要来了后台测试数据，答案完全匹配~2015/12/14/13:35】
/*
首先将走格子写成一排，即：
123...(n-1)n(n-1)(n-2)...32123...(n-1)n(n-1)(n-2)...，可见循环内容是
123...(n-1)n(n-1)(n-2)...32
周期是c=2*n-2,这样判断的目的是当m太大时，可以将m%=c,从而减少时间损耗
判断YES/NO的条件是：
当猪猪顺某个方向走时正好走到已经走过的格子，判断这时是否已经走完全部格子。
*/
#include <stdio.h>
#include <string.h>
#define maxn 100010
int a[maxn];//a[maxn]=1:该格子已被踩过;a[maxn]=0:该格子还未被踩
int main()
{//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);int n, k, i, sum;while (~scanf("%d%d", &n, &k)){if (n == 1){printf("YES\n");continue;}memset(a, 0, sizeof(a));k %= (2 * n - 2);i = 1;sum = 0;while(1){if (i <= n){//统一在方向1->n时踩到已踩过格子时退出if (a[i]) break;else a[i] = 1;}else a[2 * n - i] = 1;i += k;if (i > 2 * n - 2)i -= (2 * n - 2);}for (i = 1;i <= n;i++)sum += a[i];if (sum == n) printf("YES\n");else printf("NO\n");}return 0;
}
思路：【首先特判掉 n =1 的情况，此时必定是YES，接下来考虑 n > 1 的情况。】
考虑猪猪的行走路线，如果 n=4，那么遍历到的格子：12343212343212...，以 123432 为一个周期，其长度为 2n-2 。
做法1：由于 n <= 100000，这道题可以暴力模拟来做，不断地走直到某个位置某一朝向的情况出现两次，再推出循环。但是要考虑到 k 远大于 n 的情况下性能较差的情况，所以先将 k %= （2n-2），这样就可以通过。
做法2：由于 2n-2 是一个周期，那么可以把问题看成猪猪在一个长为 2n-2 的环里面无限地走，每次走 k 步，可以证明如果 GCD（2n-2，k）=1，可以走到所有格子。
简证：【用 GCD 代表 2n-2 和 k 的最大公约数，用 LCM 代表两者的最小公倍数】从 1 出发，不断地每次走 k 步，直到再次走到 1 形成一个周期，此时走的步数必定为 p*（2n-2），p为一个>=1的常数，易得 p*（2n-2）= LCM 那么在第二次走到1之前，总共标记了m = LCM / k 个格子，由于 LCM=（2n-2）* k / GCD，那么 m = （2n-2）/ GCD，如果 GCD>=2，那么 m < n。由上述，每个周期起点都为1，且标记的点相同，点数都为 m < n，所以 GCD >=2 时不能标记所有点，答案为NO。
接下来证明 GCD = 1 时能标记所有点，考虑另外一个问题：一个有 L 个格子的环，从 1 出发，每次跳 k 个格子能否跳到所有格子。显然重复跳到某个格子至少需要跳 LCM（L，k） 个格子（设为结论1），跳了 LCM / k 次，如果 GCD（L，K）=1，那么跳的次数为 L 次，这期间必定跳到 1~L 所有点，即证明：期间跳到的格子不重复。如果跳到的点重复，则说明重复跳到某个格子至少需要跳的格子数 < LCM，与结论1矛盾，得证。
//做法1
#include <stdio.h>
#include <string.h>const int MAX = 102400;
const int LEFT = 0;
const int RIGHT = 1;int N, K;
int pVisited[2][MAX];int main() {while (scanf("%d%d", &N, &K) != EOF) {if (N == 1) {printf("YES\n");continue;}K %= 2 * (N - 1);memset(pVisited, false, sizeof(pVisited));int nDir = RIGHT, nCur = 1;while (!pVisited[nDir][nCur]) {pVisited[nDir][nCur] = true;if (nDir == RIGHT) {nCur += K;if (nCur > N) {nCur = 2 * N - nCur;nDir = LEFT;}if (nCur < 1) {nCur = 2 - nCur;nDir = RIGHT;}}else {nCur -= K;if (nCur < 1) {nCur = 2 - nCur;nDir = RIGHT;}if (nCur > N) {nCur = 2 * N - nCur;nDir = LEFT;}}}bool bFlag = true;for (int i = 1; i <= N; i++) {if (!pVisited[LEFT][i] && !pVisited[RIGHT][i]){bFlag = false; break;}}if (bFlag) printf("YES\n");else printf("NO\n");}return 0;
}//做法2
#include <stdio.h>int n, k;int Gcd(int a, int b) {return b == 0 ? a : Gcd(b, a % b);
}int main() {while (scanf("%d%d", &n, &k) != EOF) {if (n == 1) {printf("YES\n");continue;}if (Gcd(2 * n - 2, k) == 1) printf("YES\n");else printf("NO\n");}return 0;
}