两道题目表面上看起来很相似,解法是不一样的。

ZOJ 1314 的本质是给定数 \(x, y\) ,问 \(ax (\bmod y), a = 1, 2, \cdots\) 的周期是多少。依稀记得同余理论和不定方程的某些结论,我猜测周期应该是 \(\frac{y}{gcd(x, y)}\) ,自己验证了下也是对的。具体证明涉及到同余和不定方程,高中的基础全忘了,叹。

程序 AC 一波三折,先是 TLE,后来发现 scanf() 后面没有写 != EOF ,可是这题也没说啥时算输入结束啊……看来是经验不足了;后来又是 Presentation Error,仔细检查发现是四个空格输出成了五个空格……叹……

代码:

#include <stdio.h>

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

int main(int argc, char *argv[]) {
  int step, mod;

  while (scanf("%d%d", &step, &mod) != EOF) {
    printf("%10d%10d", step, mod);

    if (gcd(step, mod) == 1) {
      printf ("    Good Choice\n");
    }
    else {
      printf ("    Bad Choice\n");
    }
    printf ("\n");
  }

  return 0;
}

ZOJ 1278 和 ZOJ 1314 很像,于是我尝试着用 ZOJ 1314 的方法去解决,我甚至求出了通项公式:

\(y\_n = (Z\^{n-1}L + \frac{Z\^{n-1} - 1}{Z - 1}I )\bmod M\)

后来发现不行,因为这个式子的增量不是线性常数,需要另觅他法。很无耻的参考了 这篇博客,难得体会到了代码之美,用数组做标记(我不知道是不是该这样说,或者 Hash Table?)的手法,某些时候确实很管用,需要进一步熟悉。

代码贴一下吧……虽然是抄袭的 ^~^

#include <iostream>
#include <cstring>
using namespace std;

int main(int argc, char *argv[]) {
  int z, i, m, last, next;
  bool judge[10000];

  int count;
  int n = 1;

  while (cin >> z >> i >> m >> last) {
    if (z == 0 && i == 0 && m == 0 && last == 0) {
      break;
    }

    memset(judge, false, sizeof(judge));

    count = 0;
    while (true) {
      next = (z * last + i) % m;

      if (judge[next]) {
        break;
      }

      last = next;
      judge[next] = true;

      count++;
    }

    cout << "Case " << n++ << ": "  << count << endl;
  }

  return 0;
}

加油加油啊。