ZOJ 1489

题目不是很难，重点是时间限制。因此需要优化下算法，不要暴力的用 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 道题目了。都是水题。不管怎样，先凑个数练练手也好。时间紧迫。一定的数量还是必须的。要不以后出去也忒没面子了。