回答編集履歴
6
test
CHANGED
|
@@ -30,6 +30,8 @@
|
|
|
30
30
|
|
|
31
31
|
という手順を踏んでいます。
|
|
32
32
|
|
|
33
|
+
---
|
|
34
|
+
|
|
33
35
|
ではNが奇数（奇数乗）の場合はどう計算すればよいのでしょうか。
|
|
34
36
|
|
|
35
37
|
たとえば N=7のとき（2^7乗を10で割った余り）の計算を考えてみましょう
|
5
test
CHANGED
|
@@ -2,19 +2,17 @@
|
|
|
2
2
|
|
|
3
3
|
たとえばN=8つまり「２^8乗を10で割った余り」を求めるとします。
|
|
4
4
|
８= 4 + 4 なので
|
|
5
|
-
「
|
|
5
|
+
「2^8乗を10で割った余り」は
|
|
6
|
-
|
|
7
|
-
|
|
6
|
+
+ （2^**4**乗を10で割った余り × 2^**4**乗を10で割った余り）を10で割った余り
|
|
8
|
-
|
|
9
7
|
と分解できます。
|
|
10
8
|
|
|
11
|
-
同様に、「
|
|
9
|
+
同様に、「2^4乗を10で割った余り」は 4=2+2 なので
|
|
12
|
-
|
|
10
|
+
+ （2^**2**乗を10で割った余り × 2^**2**乗を10で割った余り）を10で割った余り
|
|
13
11
|
で計算できます。
|
|
14
12
|
このように分解していくと最後に
|
|
15
|
-
|
|
13
|
+
+ （2^**0**乗を10で割った余り × 2^**0**乗を10で割った余り）を10で割った余り
|
|
16
|
-
|
|
14
|
+
+ ＝（1 × １）を10で割った余り
|
|
17
|
-
|
|
15
|
+
+ ＝ １
|
|
18
16
|
となります。
|
|
19
17
|
これが
|
|
20
18
|
```py
|
|
@@ -27,8 +25,8 @@
|
|
|
27
25
|
|
|
28
26
|
上の例を一般化して、プログラムでは
|
|
29
27
|
与えられた数をどんどん 2 で割っていく （ half = calc(N // 2) ）
|
|
30
|
-
→その数を10で割った余り [ calc(N // 2)] を求めて、2乗する。（res=half*half）
|
|
28
|
+
→ その数を10で割った余り [ calc(N // 2)] を求めて、2乗する。（res=half*half）
|
|
31
|
-
→res を10で割った余りを求めて返す（ return res % 10）
|
|
29
|
+
→ res を10で割った余りを求めて返す（ return res % 10）
|
|
32
30
|
|
|
33
31
|
という手順を踏んでいます。
|
|
34
32
|
|
|
@@ -38,11 +36,11 @@
|
|
|
38
36
|
|
|
39
37
|
このときは
|
|
40
38
|
7＝3＋3＋1なので
|
|
41
|
-
|
|
39
|
+
+ （2^**3**乗を10で割った余り × 2^**3**乗を10で割った余り × 2^**1**乗 を10で割った余り）を10で割った余り
|
|
42
40
|
を求めればいいわけですね。
|
|
43
41
|
|
|
44
|
-
「2^1 を10で割った余り」はすなわち 2 なので
|
|
42
|
+
3つ目の「2^**1**乗 を10で割った余り」はすなわち 2 なので
|
|
45
|
-
|
|
43
|
+
+ （2^3乗を10で割った余り × 2^3乗を10で割った余り × **２**）を10で割った余り
|
|
46
44
|
を求めることになります。
|
|
47
45
|
|
|
48
46
|
この後半の「× ２」が
|
4
test
CHANGED
|
@@ -34,7 +34,7 @@
|
|
|
34
34
|
|
|
35
35
|
ではNが奇数（奇数乗）の場合はどう計算すればよいのでしょうか。
|
|
36
36
|
|
|
37
|
-
たとえば N=7のとき（2^7乗の
|
|
37
|
+
たとえば N=7のとき（2^7乗を10で割った余り）の計算を考えてみましょう
|
|
38
38
|
|
|
39
39
|
このときは
|
|
40
40
|
7＝3＋3＋1なので
|
3
test
CHANGED
|
@@ -16,11 +16,13 @@
|
|
|
16
16
|
> ＝（1 × １）を10で割った余り
|
|
17
17
|
> ＝ １
|
|
18
18
|
となります。
|
|
19
|
+
これが
|
|
19
20
|
```py
|
|
20
21
|
# 終端条件
|
|
21
22
|
if N == 0:
|
|
22
23
|
return 1
|
|
23
24
|
```
|
|
25
|
+
の部分です。
|
|
24
26
|
|
|
25
27
|
|
|
26
28
|
上の例を一般化して、プログラムでは
|
2
test
CHANGED
|
@@ -4,17 +4,17 @@
|
|
|
4
4
|
８= 4 + 4 なので
|
|
5
5
|
「２^8乗を10で割った余り」は
|
|
6
6
|
|
|
7
|
-
（２^4乗を10で割った余り × ２^4乗を10で割った余り）を10で割った余り
|
|
7
|
+
> （２^4乗を10で割った余り × ２^4乗を10で割った余り）を10で割った余り
|
|
8
8
|
|
|
9
9
|
と分解できます。
|
|
10
10
|
|
|
11
11
|
同様に、「２^4乗を10で割った余り」は 4=2+2 なので
|
|
12
|
-
（２^2乗を10で割った余り × ２^2乗を10で割った余り）を10で割った余り
|
|
12
|
+
> （２^2乗を10で割った余り × ２^2乗を10で割った余り）を10で割った余り
|
|
13
13
|
で計算できます。
|
|
14
14
|
このように分解していくと最後に
|
|
15
|
-
（２^0乗を10で割った余り × ２^0乗を10で割った余り）を10で割った余り
|
|
15
|
+
> （２^0乗を10で割った余り × ２^0乗を10で割った余り）を10で割った余り
|
|
16
|
-
＝（1 × １）を10で割った余り
|
|
16
|
+
> ＝（1 × １）を10で割った余り
|
|
17
|
-
＝ １
|
|
17
|
+
> ＝ １
|
|
18
18
|
となります。
|
|
19
19
|
```py
|
|
20
20
|
# 終端条件
|
|
@@ -36,12 +36,13 @@
|
|
|
36
36
|
|
|
37
37
|
このときは
|
|
38
38
|
7＝3＋3＋1なので
|
|
39
|
-
（２^3乗を10で割った余り × ２^3乗を10で割った余り × **2^1 を10で割った余り**）を10で割った余り
|
|
39
|
+
> （２^3乗を10で割った余り × ２^3乗を10で割った余り × **2^1 を10で割った余り**）を10で割った余り
|
|
40
40
|
を求めればいいわけですね。
|
|
41
41
|
|
|
42
42
|
「2^1 を10で割った余り」はすなわち 2 なので
|
|
43
|
-
（２^3乗を10で割った余り × ２^3乗を10で割った余り ×**２**）を10で割った余り
|
|
43
|
+
> （２^3乗を10で割った余り × ２^3乗を10で割った余り ×**２**）を10で割った余り
|
|
44
44
|
を求めることになります。
|
|
45
|
+
|
|
45
46
|
この後半の「× ２」が
|
|
46
47
|
```py
|
|
47
48
|
if N % 2 == 1: res *= 2
|
1
test
CHANGED
|
@@ -40,9 +40,9 @@
|
|
|
40
40
|
を求めればいいわけですね。
|
|
41
41
|
|
|
42
42
|
「2^1 を10で割った余り」はすなわち 2 なので
|
|
43
|
-
（２^3乗を10で割った余り × ２^3乗を10で割った余り ×
|
|
43
|
+
（２^3乗を10で割った余り × ２^3乗を10で割った余り ×**２**）を10で割った余り
|
|
44
44
|
を求めることになります。
|
|
45
|
-
こ
|
|
45
|
+
この後半の「× ２」が
|
|
46
46
|
```py
|
|
47
47
|
if N % 2 == 1: res *= 2
|
|
48
48
|
```
|