zoj1489 - 行者无疆 始于足下 - 行走,思考,在路上

zoj1489

xiaohanyu posted @ Mon, 12 Apr 2010 02:48:06 +0800 in Algorithm with tags ZOJ , 3046 readers

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


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee