题目不是很难,重点是时间限制。因此需要优化下算法,不要暴力的用 pow(x, y) 函数。我用的是 pow(x, y) 图省事,先是出现了久违的 compilation error 。思前想后,自己的机器上编译没有问题啊。看了 ZOJ 的输出指示:

p.cc: In function 'int main(int, char**)':
p.cc:19: error: call of overloaded 'pow(int, int&)' is ambiguous
/usr/include/bits/mathcalls.h:154: note: candidates are: double pow(double, double)
/usr/include/c++/4.2/cmath:373: note:                 long double std::pow(long double, int)
/usr/include/c++/4.2/cmath:369: note:                 float std::pow(float, int)
/usr/include/c++/4.2/cmath:365: note:                 double std::pow(double, int)
/usr/include/c++/4.2/cmath:361: note:                 long double std::pow(long double, long double)
/usr/include/c++/4.2/cmath:357: note:                 float std::pow(float, float)

估计大概是 libc 版本不同造成的。修改了以下程序,又出现了 TLE 的错误了。后来想了想,利用同余特性,改进了程序,还是 TLE。程序如下:

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
  int n, temp, result;

  while(cin >> n) {
    if((n & 0x1) == 0)
      cout << "2^? mod " << n << " = 1" << endl;
    else {
      temp = 1;
      result = 1;
      while(1) {
        temp *= 2;
        temp %= n;
        if(temp == 1)
          break;
        ++result;
      }
      cout << "2^" << result << " mod " << n << " = 1" << endl;
    }
  }
  return 0;
}

这是怎么回事呢?百思不得其解。俗话说外事不决问 Google,内事不决问 Baidu。于是 Baidu 之,发现只要将判断条件改进下就行,AC 的程序如下:

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
  int n, temp, result;

  while(cin >> n) {
    if((n & 0x1) == 0 || n < 2)
      cout << "2^? mod " << n << " = 1" << endl;
    else {
      temp = 1;
      result = 1;
      while(1) {
        temp *= 2;
        temp %= n;
        if(temp == 1)
          break;
        ++result;
      }
      cout << "2^" << result << " mod " << n << " = 1" << endl;
    }
  }
  return 0;
}

一个 ~n < 2~,应该无关紧要……先记着这笔帐。

AC 了 26 道题目了。都是水题。不管怎样,先凑个数练练手也好。时间紧迫。一定的数量还是必须的。要不以后出去也忒没面子了。