質問編集履歴
4
誤字
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -5,7 +5,7 @@
|
|
|
5
5
|
ことを表している．この性質を利用します。
|
|
6
6
|
|
|
7
7
|
標準入力で与えられる整数 n に対し，フィボナッチ数列の n 番め Fn を 2018 で割った余りを標準出力に
|
|
8
|
-
出力するプログラムを作成せよ．ただし，n は
|
|
8
|
+
出力するプログラムを作成せよ．ただし，n は 10^9 以下の正の整数であると仮定してよい．
|
|
9
9
|
入力例 出力例
|
|
10
10
|
10 55
|
|
11
11
|
入力例 出力例
|
3
誤字
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -60,14 +60,11 @@
|
|
|
60
60
|
int main(void)
|
|
61
61
|
{
|
|
62
62
|
struct golden x = { 1, -1 };
|
|
63
|
-
struct golden y = { 1, -1 };
|
|
64
63
|
int i,n;
|
|
65
64
|
scanf("%d", &n);
|
|
66
|
-
for(i=1; i <= n-1; i++){
|
|
67
65
|
x = power_golden(x, i);
|
|
68
66
|
printf("%lld\n", x.a);
|
|
69
|
-
|
|
67
|
+
|
|
70
|
-
}
|
|
71
68
|
return 0;
|
|
72
69
|
}
|
|
73
70
|
|
2
誤字
title
CHANGED
|
@@ -1,1 +1,1 @@
|
|
|
1
|
-
フィボナッチ数列のn番目の剰余を求める時、値が大きくなってしまうと計算が正しく出力され
|
|
1
|
+
フィボナッチ数列のn番目の剰余を求める時、値が大きくなってしまうと計算が正しく出力されません。
|
body
CHANGED
|
File without changes
|
1
ソースコードの貼り付け
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -21,4 +21,54 @@
|
|
|
21
21
|
この問題で与えた入力nが大きくなってしまうと誤った結果を吐き出してしまいます。
|
|
22
22
|
|
|
23
23
|
おそらく値がマイナスのものに剰余を行ってしまっているからだと思うんですが、
|
|
24
|
-
改善方法が思い当たらないのでご教示願います。
|
|
24
|
+
改善方法が思い当たらないのでご教示願います。
|
|
25
|
+
```C言語
|
|
26
|
+
include<stdio.h>
|
|
27
|
+
int number = 0;
|
|
28
|
+
|
|
29
|
+
struct golden {
|
|
30
|
+
long long int a;
|
|
31
|
+
long long int b;
|
|
32
|
+
};
|
|
33
|
+
|
|
34
|
+
struct golden mult_golden(struct golden x, struct golden y) {
|
|
35
|
+
number += 1;
|
|
36
|
+
struct golden z;
|
|
37
|
+
z.a = (((x.a % 2018) * (y.a % 2018)) % 2018 + ((x.b % 2018) * (y.b % 2018)) %\
|
|
38
|
+
2018) % 2018;
|
|
39
|
+
z.b = (((x.a % 2018) * (y.b % 2018)) % 2018 + ((x.b % 2018) * (y.a % 2018)) %\
|
|
40
|
+
2018 + ((x.b % 2018) * (y.b % 2018)) % 2018) % 2018;
|
|
41
|
+
return z;
|
|
42
|
+
}
|
|
43
|
+
|
|
44
|
+
struct golden power_golden(struct golden x, int n) {
|
|
45
|
+
struct golden z;
|
|
46
|
+
|
|
47
|
+
if(n == 0) {
|
|
48
|
+
z.a = 1;
|
|
49
|
+
z.b = 0;
|
|
50
|
+
return z;
|
|
51
|
+
} else if(n % 2 == 0) {
|
|
52
|
+
z = power_golden(x, n/2);
|
|
53
|
+
return mult_golden(z, z);
|
|
54
|
+
} else {
|
|
55
|
+
z = power_golden(x, n-1);
|
|
56
|
+
return mult_golden(z, x);
|
|
57
|
+
}
|
|
58
|
+
}
|
|
59
|
+
|
|
60
|
+
int main(void)
|
|
61
|
+
{
|
|
62
|
+
struct golden x = { 1, -1 };
|
|
63
|
+
struct golden y = { 1, -1 };
|
|
64
|
+
int i,n;
|
|
65
|
+
scanf("%d", &n);
|
|
66
|
+
for(i=1; i <= n-1; i++){
|
|
67
|
+
x = power_golden(x, i);
|
|
68
|
+
printf("%lld\n", x.a);
|
|
69
|
+
x = y;
|
|
70
|
+
}
|
|
71
|
+
return 0;
|
|
72
|
+
}
|
|
73
|
+
|
|
74
|
+
```
|