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]的值吗？
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 ）
每组数据占一行，包含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
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+;
const int MAX = 1e9+;
using namespace std;
struct mat{
ll a[N][N];
mat(){
memset(a, , sizeof(a));
}
mat operator *(mat b){
mat c;
for(int i=;i<N;i++)
for(int j=;j<N;j++)
for(int k=;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=;i<N;i++)
t.a[i][i] = ;
while(m){
if(m% == ) t = t*x;
x = x*x;
m >>= ;
}
return t;
}
ll powermod(ll a, ll b, ll c){
ll ans = ;
a = a % c;
while(b>) {
if(b % == )
ans = (ans * a) % c;
b = b/;
a = (a * a) % c;
}
return ans;
}
ll eular(ll n)
{
ll ret=,i;
for(i=;i*i<=n;i++)
{
if(n%i==)
{
n/=i,ret*=i-;
while(n%i==) n/=i,ret*=i;
}
}
if(n>) ret*=n-;
return ret;
}
ll fmod(ll n){//第n项斐波那契取模
if(n==||n==-) return ;
if(n==) return ;
mat A, s;
s.a[][] = ;s.a[][] = ;
A.a[][] = A.a[][] = A.a[][] = ;
s = s*f(A, n-);
return s.a[][];
}
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-), MAX)*powermod(b, fmod(n), MAX)%MAX;
printf("%I64d\n", ans);
}
return ;
}