回答編集履歴
1
変更です
answer
CHANGED
|
@@ -2,6 +2,17 @@
|
|
|
2
2
|
|
|
3
3
|
リストを作成した上に、それを順番にxに入れるためにさらに時間が増えます。
|
|
4
4
|
|
|
5
|
-
2 正解コードでは、gcd(i, j)の計算がK**2回で済んでいるのに、時間切れコードではそれにあたる計算がK**3回必要になっています。
|
|
5
|
+
~~2 正解コードでは、gcd(i, j)の計算がK**2回で済んでいるのに、時間切れコードではそれにあたる計算がK**3回必要になっています。~~
|
|
6
6
|
|
|
7
|
-
3 正解コードでは、i,j,k をそのまま使えますが、時間切れコードではx[0],x[1],x[2]とタプルの要素アクセスになって時間がかかっています。
|
|
7
|
+
3 正解コードでは、i,j,k をそのまま使えますが、時間切れコードではx[0],x[1],x[2]とタプルの要素アクセスになって時間がかかっています。
|
|
8
|
+
|
|
9
|
+
変更です。
|
|
10
|
+
|
|
11
|
+
以下のコードだと、gcd(i, j)の計算がK^2回で済むので、正解コードより速くなります。
|
|
12
|
+
```python
|
|
13
|
+
for i in range(1, K + 1):
|
|
14
|
+
for j in range(1, K + 1):
|
|
15
|
+
gcd_ij = gcd(i, j)
|
|
16
|
+
for k in range(1, K + 1):
|
|
17
|
+
ans += gcd(gcd_ij, k)
|
|
18
|
+
```
|