UVa 11582 Colossal Fibonacci Numbers! 【大数幂取模】

题目链接：Uva 11582 [vjudge]

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">

题意

输入两个非负整数a、b和正整数n（0<=a,b<=2^64,1<=n<=1000），让你计算f（a^b）对n取模的值，当中f（0） = 0，f（1） =  1。且对随意非负整数i。f（i+2）= f（i+1）+f（i）。

分析

全部的计算都是对n取模。设F(i) =f（i）mod n， 非常easy发现，F（x）是具有周期性的，由于对N取模的值最多也就N个，当二元组（F(i-1)，F(i)）反复的时候。整个序列也就反复了。周期i – 1啊，自己能够找组小的数据研究研究，就能够发现这个规律了。

周期最大会有多大呢？因为余数最多也就N个。那么最多N^2就会反复，全然能够才时限内攻克了。

剩下的知识就是针对高速幂取模了，这个在我另外一篇博客《超级高速幂【费马小定理】+【高速幂取模】》里面有比較具体的介绍。

參考代码

/****************************>>>>HEADFILES<<<<****************************/

#include <set>

#include <map>

#include <list>

#include <cmath>

#include <queue>

#include <vector>

#include <cstdio>

#include <string>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <sstream>

#include <algorithm>

using namespace std;

/****************************>>>>>DEFINE<<<<<*****************************/

#define fst             first

#define snd             second

#define root            1,N,1

#define lson            l,mid,rt<<1

#define rson            mid+1,r,rt<<1|1

#define PB(a)           push_back(a)

#define MP(a,b)         make_pair(a,b)

#define CASE(T)         for(scanf("%d",&T);T--;)

#define FIN             freopen("input.txt","r",stdin)

#define FOUT            freopen("output.txt","w",stdout)

//#pragma comment(linker, "/STACK:1024000000,1024000000")

//typedef unsigned __int64 ull;

typedef unsigned long long ull;

typedef pair<int, int>   pii;

const int INF = 0x3f3f3f3f;

const int maxn = 1000 + 5;

const int maxm = 20000 + 5;

/****************************>>>>SEPARATOR<<<<****************************/

int T, N;

ull a, b;

int ans[maxn*maxn];

int Fibo(const int& MOD)

{

    int ret;

    ans[0] = 0, ans[1] = 1 % MOD;

    int i = 2;

    while(1)

    {

        ans[i] = (ans[i - 1] + ans[i - 2]) % MOD;

        if(ans[i - 1] == 0 && ans[i] == 1 % MOD) break;

        i++;

    }

    return i - 1;

}

int pow_mod(ull x, ull y, int MOD)

{

    ull ret = 1;

    while(y)

    {

        if(y & 1) ret = (ret * x) % MOD;

        x = (x * x) % MOD;

        y >>= 1;

    }

    return (int)ret;

}

int main()

{

//    FIN;

    CASE(T)

    {

        scanf("%llu %llu %d",&a,&b,&N);

        if(a == 0 || N == 1)

        {

            printf("0\n");

            continue;

        }

        int Cyc = Fibo(N);

        int pos = pow_mod(a % Cyc, b, Cyc);

        printf("%d\n",ans[pos]);

    }

    return 0;

}