回答編集履歴
6
コード追記
answer
CHANGED
|
@@ -31,4 +31,11 @@
|
|
|
31
31
|
}
|
|
32
32
|
return ret;
|
|
33
33
|
}
|
|
34
|
-
```
|
|
34
|
+
```
|
|
35
|
+
|
|
36
|
+
---
|
|
37
|
+
`a == 0`の場合が考慮されていないのが原因なので、`modPow`の先頭に
|
|
38
|
+
```C++
|
|
39
|
+
if (a == 0) return 1;
|
|
40
|
+
```
|
|
41
|
+
を書けば再帰でも通ると思います。
|
5
文言修正
answer
CHANGED
|
@@ -12,7 +12,7 @@
|
|
|
12
12
|
---
|
|
13
13
|
> modPowという関数についてですが、この部分は別の機会で作ったものでこれまでも正しく動作していたので恐らく問題はないと思います。またこのmodPowとは別のアルゴリズムでべき乗計算を行うコードを提出しても同じケースでREとなりましたので
|
|
14
14
|
|
|
15
|
-
[以前私が回答で貼った`modPow`](https://teratail.com/questions/286455#reply-406659)に差し替えて実行すると正解の`1`が返りますが、これでもだめですか？
|
|
15
|
+
[以前私が回答で貼った`modPow`](https://teratail.com/questions/286455#reply-406659)に差し替えて実行すると正解の`1`が返りますが、これでもだめですか？(提出しての確認はしていません)
|
|
16
16
|
```C++
|
|
17
17
|
ll modPow(ll x, ll a)
|
|
18
18
|
{
|
4
文言修正
answer
CHANGED
|
@@ -12,7 +12,7 @@
|
|
|
12
12
|
---
|
|
13
13
|
> modPowという関数についてですが、この部分は別の機会で作ったものでこれまでも正しく動作していたので恐らく問題はないと思います。またこのmodPowとは別のアルゴリズムでべき乗計算を行うコードを提出しても同じケースでREとなりましたので
|
|
14
14
|
|
|
15
|
-
[以前私が回答で貼った`modPow`](https://teratail.com/questions/286455#reply-406659)に差し替えて実行すると`1`が返りますが、これでもだめですか？
|
|
15
|
+
[以前私が回答で貼った`modPow`](https://teratail.com/questions/286455#reply-406659)に差し替えて実行すると正解の`1`が返りますが、これでもだめですか？
|
|
16
16
|
```C++
|
|
17
17
|
ll modPow(ll x, ll a)
|
|
18
18
|
{
|
3
コード追記
answer
CHANGED
|
@@ -7,4 +7,28 @@
|
|
|
7
7
|
return (t * t) % MOD;
|
|
8
8
|
}
|
|
9
9
|
```
|
|
10
|
-
で`modPow(2, 0)`を無限に呼び続けています。
|
|
10
|
+
で`modPow(2, 0)`を無限に呼び続けています。
|
|
11
|
+
|
|
12
|
+
---
|
|
13
|
+
> modPowという関数についてですが、この部分は別の機会で作ったものでこれまでも正しく動作していたので恐らく問題はないと思います。またこのmodPowとは別のアルゴリズムでべき乗計算を行うコードを提出しても同じケースでREとなりましたので
|
|
14
|
+
|
|
15
|
+
[以前私が回答で貼った`modPow`](https://teratail.com/questions/286455#reply-406659)に差し替えて実行すると`1`が返りますが、これでもだめですか？
|
|
16
|
+
```C++
|
|
17
|
+
ll modPow(ll x, ll a)
|
|
18
|
+
{
|
|
19
|
+
long long ret = 1;
|
|
20
|
+
x %= MOD;
|
|
21
|
+
while (0 < a)
|
|
22
|
+
{
|
|
23
|
+
if (a % 2 == 0) {
|
|
24
|
+
x = (x * x) % MOD;
|
|
25
|
+
a /= 2;
|
|
26
|
+
}
|
|
27
|
+
else {
|
|
28
|
+
ret = (ret * x) % MOD;
|
|
29
|
+
--a;
|
|
30
|
+
}
|
|
31
|
+
}
|
|
32
|
+
return ret;
|
|
33
|
+
}
|
|
34
|
+
```
|
2
コード追記
answer
CHANGED
|
@@ -1,4 +1,10 @@
|
|
|
1
1
|
[REになっているケースの入力](https://www.dropbox.com/sh/arnpe0ef5wds8cv/AACiVu2IaOWRgMEWVrY78Sr4a/ARC066/C/in?preview=subtask_1_min_valid_01.txt)を入れてデバッガで追えば一発です。
|
|
2
2
|
|
|
3
3
|
`N`が`1`で`ans = modPow(2, N / 2);`を呼んでしまっているため、
|
|
4
|
+
```C++
|
|
5
|
+
if (a % 2 == 0) {
|
|
6
|
+
ll t = modPow(x, a / 2);
|
|
7
|
+
return (t * t) % MOD;
|
|
8
|
+
}
|
|
9
|
+
```
|
|
4
|
-
`modPow(2, 0)`を無限に呼び続けています。
|
|
10
|
+
で`modPow(2, 0)`を無限に呼び続けています。
|
1
リンク削除
answer
CHANGED
|
@@ -1,5 +1,4 @@
|
|
|
1
|
-
[提出 #16428925](https://atcoder.jp/contests/abc050/submissions/16428925)
|
|
2
|
-
|
|
1
|
+
[REになっているケースの入力](https://www.dropbox.com/sh/arnpe0ef5wds8cv/AACiVu2IaOWRgMEWVrY78Sr4a/ARC066/C/in?preview=subtask_1_min_valid_01.txt)を入れてデバッガで追えば一発です。
|
|
3
2
|
|
|
4
3
|
`N`が`1`で`ans = modPow(2, N / 2);`を呼んでしまっているため、
|
|
5
4
|
`modPow(2, 0)`を無限に呼び続けています。
|