回答編集履歴
1
変更です
test
CHANGED
|
@@ -6,8 +6,30 @@
|
|
|
6
6
|
|
|
7
7
|
|
|
8
8
|
|
|
9
|
-
2 正解コードでは、gcd(i, j)の計算がK**2回で済んでいるのに、時間切れコードではそれにあたる計算がK**3回必要になっています。
|
|
9
|
+
~~2 正解コードでは、gcd(i, j)の計算がK**2回で済んでいるのに、時間切れコードではそれにあたる計算がK**3回必要になっています。~~
|
|
10
10
|
|
|
11
11
|
|
|
12
12
|
|
|
13
13
|
3 正解コードでは、i,j,k をそのまま使えますが、時間切れコードではx[0],x[1],x[2]とタプルの要素アクセスになって時間がかかっています。
|
|
14
|
+
|
|
15
|
+
|
|
16
|
+
|
|
17
|
+
変更です。
|
|
18
|
+
|
|
19
|
+
|
|
20
|
+
|
|
21
|
+
以下のコードだと、gcd(i, j)の計算がK^2回で済むので、正解コードより速くなります。
|
|
22
|
+
|
|
23
|
+
```python
|
|
24
|
+
|
|
25
|
+
for i in range(1, K + 1):
|
|
26
|
+
|
|
27
|
+
for j in range(1, K + 1):
|
|
28
|
+
|
|
29
|
+
gcd_ij = gcd(i, j)
|
|
30
|
+
|
|
31
|
+
for k in range(1, K + 1):
|
|
32
|
+
|
|
33
|
+
ans += gcd(gcd_ij, k)
|
|
34
|
+
|
|
35
|
+
```
|