[HDU 4549]Mフィボナッチ数列
7452 ワード
Mフィボナッチ数列
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1609 Accepted Submission(s): 460
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
複数のテストデータを含む入力;
各グループのデータは1行を占め、3つの整数a,b,n(0<=a,b,n<=10^9)を含む.
Output
テストデータのセットごとに整数F[n]を出力してください.F[n]が大きい可能性があるので、F[n]の1000000007型取り後の値を出力するだけで、データのセットごとに1行出力できます.
Sample Input
0 1 0 6 10 2
Sample Output
0 60
Source
2013金山西山居クリエイティブゲームプログラム挑戦試合-初戦(2)
詳細:
F(n)=F(n-1)*F(n-2)F(1)=a;F(2)=b;F(3)=a^1*b^1 F(4)=a^1*b^2 F(5)=a^2*b^3 F(6)=a^3*b^5 F(n)=a^f(n'-1)*b^f(n'),f(n')はフィボラチ数列
これによりF(n)対応f(n′)、f(n′−1)を先に算出し、さらに高速べき乗を2分し、F(n)=a^f(n′−1)%MOD*b^f(n′)%MOD(n′)%MODを2分し、またnが比較的大きくMODが質量数であるため、フェルマ小の定理に基づいてF(n)=a^(f(n′−1)%(MOD−1)%MOD)*b^(f(n′)%(n′)%(MOD−1)%MODここでn′とnが異なることに注意し、nが3の場合、f(n(n′)=1とし、n′=n′=n n′=2をn′=n n−2とし...
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1609 Accepted Submission(s): 460
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
複数のテストデータを含む入力;
各グループのデータは1行を占め、3つの整数a,b,n(0<=a,b,n<=10^9)を含む.
Output
テストデータのセットごとに整数F[n]を出力してください.F[n]が大きい可能性があるので、F[n]の1000000007型取り後の値を出力するだけで、データのセットごとに1行出力できます.
Sample Input
0 1 0 6 10 2
Sample Output
0 60
Source
2013金山西山居クリエイティブゲームプログラム挑戦試合-初戦(2)
詳細:
F(n)=F(n-1)*F(n-2)F(1)=a;F(2)=b;F(3)=a^1*b^1 F(4)=a^1*b^2 F(5)=a^2*b^3 F(6)=a^3*b^5 F(n)=a^f(n'-1)*b^f(n'),f(n')はフィボラチ数列
これによりF(n)対応f(n′)、f(n′−1)を先に算出し、さらに高速べき乗を2分し、F(n)=a^f(n′−1)%MOD*b^f(n′)%MOD(n′)%MODを2分し、またnが比較的大きくMODが質量数であるため、フェルマ小の定理に基づいてF(n)=a^(f(n′−1)%(MOD−1)%MOD)*b^(f(n′)%(n′)%(MOD−1)%MODここでn′とnが異なることに注意し、nが3の場合、f(n(n′)=1とし、n′=n′=n n′=2をn′=n n−2とし...
#include <iostream>
#include <cstdio>
using namespace std;
#define MOD 1000000007
#define ll __int64
#define N 2
ll quickadd(ll a,ll b) // ， ，
{
ll ret=0;
while(b)
{
if(b&1)
{
ret+=a;
if(ret>=MOD) ret-=MOD;
}
a<<=1;
if(a>=MOD) a-=MOD;
b>>=1;
}
return ret;
}
ll quickpow(ll a,ll b) //
{
ll ret=1;
while(b)
{
if (b&1) ret=quickadd(a,ret);
a=quickadd(a,a);
b>>=1;
}
return ret;
}
void mul(ll a[N][N],ll b[N][N]) //
{
ll i,j,k;
ll c[N][N]={0};
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
for(k=0;k<N;k++)
{
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%(MOD-1);
}
}
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
a[i][j]=c[i][j];
}
}
}
int main()
{
ll A,B,n;
while(scanf("%I64d%I64d%I64d",&A,&B,&n)!=EOF)
{
if(n==0) printf("%I64d
",A%MOD);
else if(n==1) printf("%I64d
",B%MOD); // 0,1
else
{
n-=2;
ll a[N][N]={1,1},b[N][N]={0,1,1,1};
while(n)
{
if(n&1)mul(a,b);
mul(b,b);
n>>=1;
}
ll k1=a[0][0];
ll k2=a[0][1];
ll ans=1;
ans=ans*quickpow(A,k1)%MOD;
ans=ans*quickpow(B,k2)%MOD;
printf("%I64d
",ans);
}
}
return 0;
}