POJ 3070 – 快速幂取模

以前从没有对O（log N）和O（N）的区别有所正确认识，今日总算知道了。它们的唯一区别就是，N是一亿的时候，log(N)就是不到26，N还是一亿。 POJ的这道题虽然容易，但的确很有意思。我也是第一次用快速幂取模，一用，果然不同凡响。 快速幂取模，其实就是秦九韶算法 取指数。 把n化成二进制形式后，得到一个多项式,写成秦九韶形式，多项式的加就是乘，乘则为指数运算（指数为2）。由于N的二进制位个数为log(n),这样把O（N）的问题化为O（log N）。

//PKU 3070 ,calculate Fibonacci 
#include<iostream>
#include<stack>
int FPM(int); // fast-power-modulus function declare
using namespace std;
const int Mod = 10000;
int main(int argc, char *argv[])
{
    int n = 0;
    while(scanf("%d", &n))
    {
        if(n == -1)
            break;
        printf("%dn", FPM(n));
    }
    return 0;
}

int FPM(int n)//fast-power-modulus function
{
    int matr[4] = {1, 0, 0, 1}; // initialize matrix
    stack<bool>dec; // stack to store binary digit
    while(n) // resolve n to binary digit
    {
        dec.push(1&n);//get the last binary digit
        n >>= 1;
    }
    while(!dec.empty())
    {
     // matrix square
        matr[1] = ((matr[0]+matr[3])*matr[1])%Mod;
        matr[0] =(matr[0]*matr[0]+matr[2]*matr[2])%Mod;
        matr[3] =(matr[3] * matr[3] + matr[2] * matr[2]) % Mod;
        matr[2] = matr[1];
    // matrix multiply,
        if(dec.top())
        {
            matr[0] = (matr[0] + matr[1])%Mod;
            matr[1] = (matr[1] + matr[3])%Mod;
            matr[3] = matr[2];
            matr[2] = matr[1];
        }
        dec.pop();
    }
    return matr[1];//matr[1] is the result F[N]
}