NBUT 1481
1628 ワード
に言及
問題の説明
F0=0, F1=1, F2=1, F3=2, F4=3, F5=5……
Fn = F(n-1) + F(n-2) ( n >= 2)
入力
整数n(0<=n<=10000000)を入力します.
しゅつりょく
出力Fn mod 20130719
問題の説明
F0=0, F1=1, F2=1, F3=2, F4=3, F5=5……
Fn = F(n-1) + F(n-2) ( n >= 2)
入力
整数n(0<=n<=10000000)を入力します.
しゅつりょく
出力Fn mod 20130719
#include<stdio.h>
int f[1000000];
int main()
{
int a,b,c,i,j;
f[0]=0;
f[1]=1;
for(i=2; i<=572889; i++)
f[i]=(f[i-1]+f[i-2])%20130719;
while(scanf("%d",&a)!=EOF)
{
printf("%d
",f[a%572880]);
}
return 0;
}
:
#include<stdio.h>
#define N 20130719
struct matrix
{
long long s[3][3];
} A, B, D;
matrix mul(matrix D, matrix A)
{
int i, j, k;
matrix s;
for(i = 0; i < 2; i++)
for(j = 0; j < 2; j++)
{
s.s[i][j] = 0;
for(k = 0; k < 2; k++)
s.s[i][j] = (s.s[i][j] + D.s[i][k] * A.s[k][j]) % N;
}
return s;
}
matrix pow(matrix A, long long k)
{
matrix s , D = A;
s.s[0][0] = 1;
s.s[0][1] = 0;
s.s[1][0] = 0;
s.s[1][1] = 1;
while(k > 0)
{
if(k & 1) s = mul(D, s);
D = mul(D, D);
k = k >> 1;
}
return s;
}
int main ()
{
long long n;
while(scanf("%lld", &n) != EOF)
{
if(n == 0)
{
printf("0
");
continue;
}
if(n == 1)
{
printf("1
");
continue;
}
A.s[0][0] = 1;
A.s[0][1] = 1;
A.s[1][0] = 1;
A.s[1][1] = 0;
B = pow(A,n);
printf("%d
",B.s[0][1]%N);
}
return 0;
}