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
#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; }