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

• Relative Posts