• 如果喜欢本站,您可以按CTRL+D收藏本站,方便下次访问。

  • 欢迎来自五湖四海的朋友,期待为您分享有价值的资源 :oops:

POJ 3070 – 快速幂取模

POJ解题 第四度 11年前 (2009-08-16) 29次浏览 0个评论 扫描二维码

file

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

//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]
}

本网站采用BY-NC-SA 4.0协议进行授权 | 转载请注明原文链接:https://www.disidu.com/post/0903.html
如果觉得本文对您有帮助或者您心情好~可以微信打赏支持一下本站:↓↓↓
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址