teratail
回答率
85.37%
teratail 10th-anniversary
teratail 10th-anniversary
質問するログイン新規登録
トップに関する質問【C++】大きな数の階乗計算が途中で止まってしまう

編集履歴

質問編集履歴

5

打消し

2020/08/27 12:40

投稿

shukrin
shukrin

スコア14

test CHANGED
File without changes
test CHANGED
@@ -16,11 +16,11 @@
16
16
 
17
17
  (8/27追記)
18
18
 
19
- 皆様ご回答ありがとうございます。お返事が遅くなってしまい大変申し訳ありません。皆様のアドバイスをもとにループを使う方式と、末尾再帰を用いる方式の2パターンで試してみました。末尾再帰を用いる方式ではn が100万を超えるような大きさの問題でも途中で止まることなく計算ができるようです。一方でループを用いる方式では、n が20万程度のところでループがストップしてしまうようです。どちらにせよ今回はn が10万以下の想定なので問題はありませんが、後学のためにこのような差異が表れた原因についてお教えいただけますと幸いです。
20
-
21
-
22
-
23
- 最初に作成した末尾再帰のコードは配列に階乗の値を格納することができなかったため、配列に値を格納できるよう末尾再帰を書き直しました。しかしこのコードもまたn が10万強のところでストップしてしまうようです。
19
+ 皆様ご回答ありがとうございます。お返事が遅くなってしまい大変申し訳ありません。皆様のアドバイスをもとにループを使う方式と、末尾再帰を用いる方式の2パターンで試してみました。~~末尾再帰を用いる方式ではn が100万を超えるような大きさの問題でも途中で止まることなく計算ができるようです。一方でループを用いる方式では、n が20万程度のところでループがストップしてしまうようです。どちらにせよ今回はn が10万以下の想定なので問題はありませんが、後学のためにこのような差異が表れた原因についてお教えいただけますと幸いです。~~
20
+
21
+
22
+
23
+ ~~最初に作成した末尾再帰のコードは配列に階乗の値を格納することができなかったため、配列に値を格納できるよう末尾再帰を書き直しました。しかしこのコードもまたn が10万強のところでストップしてしまうようです。~~
24
24
 
25
25
 
26
26
 

4

問題の解決

2020/08/27 12:40

投稿

shukrin
shukrin

スコア14

test CHANGED
File without changes
test CHANGED
@@ -24,6 +24,10 @@
24
24
 
25
25
 
26
26
 
27
+ 大変初歩的なミスでお恥ずかしい限りなのですが、回答者様からご指摘をいただき MAX_N を書き換えていなかったことが原因と分かりました。そのために配列へのアクセスのある関数は途中で止まってしまったようです。MAX_N をもっと大きな値で書き換えた場合、MAX_N 以下の n では末尾再帰、ループともに正常に動作することを確認いたしました。
28
+
29
+
30
+
27
31
  ### 該当のソースコード
28
32
 
29
33
 

3

コードの追記

2020/08/27 12:38

投稿

shukrin
shukrin

スコア14

test CHANGED
File without changes
test CHANGED
@@ -20,6 +20,10 @@
20
20
 
21
21
 
22
22
 
23
+ 最初に作成した末尾再帰のコードは配列に階乗の値を格納することができなかったため、配列に値を格納できるよう末尾再帰を書き直しました。しかしこのコードもまたn が10万強のところでストップしてしまうようです。
24
+
25
+
26
+
23
27
  ### 該当のソースコード
24
28
 
25
29
 
@@ -176,6 +180,54 @@
176
180
 
177
181
 
178
182
 
183
+ 末尾再帰＋配列格納(modFactor(n, 0, 1) を呼ぶとn! までの階乗とその逆元が全て求まるようにしました)
184
+
185
+ ```C++
186
+
187
+ long long modFactor(long long n, long long i, long long f)
188
+
189
+ {
190
+
191
+ modfac[i] = f;
192
+
193
+ if (n == i) {
194
+
195
+ modfacinv[n] = modPow(modfac[n], MOD - 2);
196
+
197
+ modFactorInv(n, modfacinv[n]);
198
+
199
+ return f;
200
+
201
+ }
202
+
203
+ return modFactor(n, i + 1, ((i + 1) * f) % MOD);
204
+
205
+ }
206
+
207
+
208
+
209
+ long long modFactorInv(long long i, long long f)
210
+
211
+ {
212
+
213
+ if (i == 0) {
214
+
215
+ modfacinv[i] = f;
216
+
217
+ return f;
218
+
219
+ }
220
+
221
+ modfacinv[i] = f;
222
+
223
+ return modFactorInv(i - 1, (i * f) % MOD);
224
+
225
+ }
226
+
227
+ ```
228
+
229
+
230
+
179
231
  ループを用いる方式((M - 1)! の逆元がM(M!)^-1 で求められることを用いています)
180
232
 
181
233
  ```C++

2

コードの追記

2020/08/27 11:56

投稿

shukrin
shukrin

スコア14

test CHANGED
File without changes
test CHANGED
@@ -14,6 +14,12 @@
14
14
 
15
15
 
16
16
 
17
+ (8/27追記)
18
+
19
+ 皆様ご回答ありがとうございます。お返事が遅くなってしまい大変申し訳ありません。皆様のアドバイスをもとにループを使う方式と、末尾再帰を用いる方式の2パターンで試してみました。末尾再帰を用いる方式ではn が100万を超えるような大きさの問題でも途中で止まることなく計算ができるようです。一方でループを用いる方式では、n が20万程度のところでループがストップしてしまうようです。どちらにせよ今回はn が10万以下の想定なので問題はありませんが、後学のためにこのような差異が表れた原因についてお教えいただけますと幸いです。
20
+
21
+
22
+
17
23
  ### 該当のソースコード
18
24
 
19
25
 
@@ -141,3 +147,85 @@
141
147
  ### 試したこと
142
148
 
143
149
  関数 modfactor の中の modfacinv[n] = (modPow(n, MOD - 2) * modfacinv[n - 1]) % MOD; の記述を消したところ n = 65139 まで正常に計算できるようになりました。このプログラムでは modfacinv は使っていませんが、元々コンビネーションの計算用に作っていたプログラムなのでこちらも計算できるようにしたいと思っています。
150
+
151
+
152
+
153
+
154
+
155
+ ###(8/27追記)
156
+
157
+ 末尾再帰を用いる方式
158
+
159
+ ```C++
160
+
161
+ long long modfactor(long long n, long long f)
162
+
163
+ {
164
+
165
+ if (n == 1) {
166
+
167
+ return f;
168
+
169
+ }
170
+
171
+ return modfactor(n - 1, (n * f) % MOD);
172
+
173
+ }
174
+
175
+ ```
176
+
177
+
178
+
179
+ ループを用いる方式((M - 1)! の逆元がM(M!)^-1 で求められることを用いています)
180
+
181
+ ```C++
182
+
183
+ // n!を求める
184
+
185
+ long long modfactor(long long n)
186
+
187
+ {
188
+
189
+ modfac[0] = 1;
190
+
191
+ long long p = 1;
192
+
193
+ while (p <= n) {
194
+
195
+ //cout << p << "\n";
196
+
197
+ modfac[p] = (p * modfac[p - 1]) % MOD;
198
+
199
+ p++;
200
+
201
+ }
202
+
203
+ modfacinv[n] = modPow(modfac[n], MOD - 2);
204
+
205
+ modfactorInv(n);
206
+
207
+ return modfac[n];
208
+
209
+ }
210
+
211
+
212
+
213
+ // (n!)^-1 を求める
214
+
215
+ void modfactorInv(long long n)
216
+
217
+ {
218
+
219
+ long long p = n - 1;
220
+
221
+ while (p >= 0) {
222
+
223
+ modfacinv[p] = ((p + 1) * modfacinv[p + 1]) % MOD;
224
+
225
+ p--;
226
+
227
+ }
228
+
229
+ }
230
+
231
+ ```

1

コード内のコメントの修正

2020/08/27 10:31

投稿

shukrin
shukrin

スコア14

test CHANGED
File without changes
test CHANGED
@@ -2,7 +2,7 @@
2
2
 
3
3
 
4
4
 
5
- nを入力として受け取り、n! を 1000000007（10^9 + 7）でわった余りを表示するプログラムを作ろうとしています。nの大きさとしては10万以下を想定しているのですが、nが数万程度以上になると急にプログラムが正常に動作しなくなるという問題が発生しています。原因を突き止めて正常に動作させたいと思っています。
5
+ nを入力として受け取り、n! を 1000000007（10^9 + 7）で割った余りを表示するプログラムを作ろうとしています。nの大きさとしては10万以下を想定しているのですが、nが数万程度以上になると急にプログラムが正常に動作しなくなるという問題が発生しています。原因を突き止めて正常に動作させたいと思っています。
6
6
 
7
7
 
8
8
 
@@ -52,7 +52,7 @@
52
52
 
53
53
  long long modPow(long long x, long long a);
54
54
 
55
- long long modfactor(long long p);
55
+ long long modfactor(long long n);
56
56
 
57
57
 
58
58
 
@@ -82,7 +82,7 @@
82
82
 
83
83
 
84
84
 
85
- // x^a　をMODで割ったあまりを求める
85
+ // x^a　をMODで割った余りを求める
86
86
 
87
87
  long long modPow(long long x, long long a)
88
88
 
@@ -110,7 +110,7 @@
110
110
 
111
111
 
112
112
 
113
- // n!を求める
113
+ // n! をMODで割った余りを求める
114
114
 
115
115
  long long modfactor(long long n)
116
116