フィボナッチ数列とは,F0 = 0,F1 = 1,Fn = Fn−1 + Fn−2 (n ≥ 2) で定義される数列であり,以下の等
式が成り立つことを簡単に示せる:
(1 − φ)^(n−1) = Fn − Fn−1φ
この等式は,「(1 − φ)^(n−1) を a + b φ (a, b は整数) の形で表したときの a が Fn そのものである」という
ことを表している.この性質を利用します。
標準入力で与えられる整数 n に対し,フィボナッチ数列の n 番め Fn を 2018 で割った余りを標準出力に
出力するプログラムを作成せよ.ただし,n は 10^9 以下の正の整数であると仮定してよい.
入力例 出力例
10 55
入力例 出力例
100 1705
入力例 出力例
1000000000 1997
なおn + m を d で割った余りは,「n を d で割った余り」と「m を d で割った余り」を足したものを d で
割った余りに等しい.
• n × m を d で割った余りは,「n を d で割った余り」と「m を d で割った余り」を掛けたものを d で
割った余りに等しい.
この問題で与えた入力nが大きくなってしまうと誤った結果を吐き出してしまいます。
おそらく値がマイナスのものに剰余を行ってしまっているからだと思うんですが、
改善方法が思い当たらないのでご教示願います。
C言語
1include<stdio.h> 2int number = 0; 3 4struct golden { 5 long long int a; 6 long long int b; 7}; 8 9struct golden mult_golden(struct golden x, struct golden y) { 10 number += 1; 11 struct golden z; 12 z.a = (((x.a % 2018) * (y.a % 2018)) % 2018 + ((x.b % 2018) * (y.b % 2018)) %\ 13 2018) % 2018; 14 z.b = (((x.a % 2018) * (y.b % 2018)) % 2018 + ((x.b % 2018) * (y.a % 2018)) %\ 15 2018 + ((x.b % 2018) * (y.b % 2018)) % 2018) % 2018; 16 return z; 17} 18 19struct golden power_golden(struct golden x, int n) { 20 struct golden z; 21 22 if(n == 0) { 23 z.a = 1; 24 z.b = 0; 25 return z; 26 } else if(n % 2 == 0) { 27 z = power_golden(x, n/2); 28 return mult_golden(z, z); 29 } else { 30 z = power_golden(x, n-1); 31 return mult_golden(z, x); 32 } 33} 34 35int main(void) 36{ 37 struct golden x = { 1, -1 }; 38 int i,n; 39 scanf("%d", &n); 40 x = power_golden(x, i); 41 printf("%lld\n", x.a); 42 43 return 0; 44} 45
回答2件
あなたの回答
tips
プレビュー