HDU4549 M斐波那契数列 矩阵快速幂+欧拉函数+欧拉定理

M斐波那契数列

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 3024    Accepted Submission(s): 930

Problem Description

M斐波那契数列F[n]是一种整数数列，它的定义如下：
F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )
现在给出a, b, n，你能求出F[n]的值吗？

 

Input

输入包含多组测试数据；
每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）

 

Output

对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。

 

Sample Input

0 1 0

6 10 2

 

Sample Output

0 60

 

题意：斐波那契数列变形

题解：很容易可以看出F[N] = b^(f(n))*a^(f(n-1))

f(n)为斐波那契数列第n项

接着求；b^(f(n))%mod == b^(t)%mod 　　(f(n)%y(mod) == t)

证：

根据欧拉函数求得y(mod)

 设 t = f(n)%y(mod)

　　f(n) = k*y(mod)+t

欧拉定理:

　　b^(y(mod))%mod == 1 (mod与b互质)

既b^(f(n))%mod == b^(k*y(mod)+t)%mod == b^(t)%mod

求t即可

t用矩阵快速幂可以求出

#include<bits/stdc++.h>
#define N 2
#define mes(x) memset(x, 0, sizeof(x));
#define ll __int64
long long mod = 1e9+7;
const int MAX = 1e9+7;
using namespace std;
struct mat{
    ll a[N][N];
    mat(){
        memset(a, 0, sizeof(a));
    }
    mat operator *(mat b){
        mat c;
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                for(int k=0;k<N;k++)
                c.a[i][j] = (c.a[i][j]+a[i][k]*b.a[k][j])%mod;
        return c;
    }
};
mat f(mat x,ll m){
    mat t;
    for(int i=0;i<N;i++)
        t.a[i][i] = 1;
    while(m){
        if(m%2 == 1) t = t*x;
        x = x*x;
        m >>= 1;
    }
    return t;
}
ll powermod(ll a, ll b, ll c){
    ll ans = 1;
    a = a % c;
    while(b>0) {
        if(b % 2 == 1)
        ans = (ans * a) % c;
        b = b/2;
        a = (a * a) % c;
    }
    return ans;
}
ll eular(ll n)
{
    ll ret=1,i;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            n/=i,ret*=i-1;
            while(n%i==0) n/=i,ret*=i;
        }
    }
    if(n>1) ret*=n-1;
    return ret;
}
ll fmod(ll n){//第n项斐波那契取模
    if(n==1||n==-1) return 1; 
    if(n==0) return 0;
    mat A, s;
    s.a[0][0] = 1;s.a[0][1] = 1;
    A.a[0][0] = A.a[1][0] = A.a[0][1] = 1;
    s = s*f(A, n-2);
    return s.a[0][0];
}
int main()
{
    ll n, a, b, ans;
    mod = eular(mod);
    while(~scanf("%I64d%I64d%I64d", &a, &b, &n)){
        //F(n) = a^(f(n-1))*b^(f(n));
        ans = powermod(a, fmod(n-1), MAX)*powermod(b, fmod(n), MAX)%MAX;
        printf("%I64d
", ans);
    }
    return 0;
}