AtCoder Beginner Contest 162 C を Python で

引き続き，AtCoder Beginner Contest 162 C を Python で解説していきたいと思います。
今回はなかなかジャッジが遅かったようで，この問題十分くらいジャッジが出ずになかなか焦りました。(-_-;)
gcd の処理もちょっと抜けていて手がすぐには動かなかったので，それも反省です。
それではもう早速解説に進みます。
まずは問題文から。
https://atcoder.jp/contests/abc162/tasks/abc162_c

---

C – Sum of gcd of Tuples (Easy)

---

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

 を求めてください。

ただし、gcd(a,b,c) は a,b,cの最大公約数を表します。

制約

• 1≤K≤200
• K は整数

---

入力

入力は以下の形式で標準入力から与えられる。

K

出力

の値を出力せよ。

---

入力例 1 

2

出力例 1

9

gcd(1,1,1) + gcd(1,1,2) + gcd(1,2,1) + gcd(1,2,2) + gcd(2,1,1) + gcd(2,1,2) + gcd(2,2,1) + gcd(2,2,2) =1+1+1+1+1+1+1+2=9=1+1+1+1+1+1+1+2=9

となるため、答えは 9 です。

---

入力例 2

200

出力例 2

10813692

---

解説

１から K までの３つの数 a,b,c のそれぞれの gcd（最大公約数）の和の値を出せと言った問題です。
Σが出てきてぱっと見少しいかついですが，入力例を見てもらえばどういうことか分かると思います。
a，ｂ，ｃ の選び方はそれぞれ１～K あるので，全体として K^3 個の組み合わせがあります。

まずは肝心の最大公約数についてです。
これについては別途記事を書きたいと思いますので，記事を書いたらまたそちらを参考にしてください。
なので，簡単に触れていきます。

最大公約数を求める際は高校数学で扱ったユークリッドの互除法を用いればよいです。
これについて復習すると，整数 a を b で割った商が c で余りが d であった時，すなわち
a = b × c + d
のとき，gcd(a,b) = gcd(b,d)
という関係が成り立つというものでした。
これを用いて，２つの数字の最大公約数を求める関数を次のように定義することができます。

# a >= b でのgcd(a,b)
def gcd2(a,b):
    if b == 0:
        return a
    return gcd2(b,a%b)

２つの数字の最大公約数ということで，関数名を gcd2 と定義しました。
これで２つの数字の間の最大公約数を求める関数が作れました。
これを３つの数字の間の最大公約数を求めようとすると，まず２つの数字の間の最大公約数を求めて，その最大公約数と３つ目の数字との最大公約数を求めればよいです。つまり
gcd(a,b,c) = gcd(gcd(a,b), c)
というわけです。これより，３つの数字の最大公約数を作る関数を次のように定義します。

def gcd3(a,b,c):
    return gcd2(gcd2(a,b), c)

これで最大公約数を求める関数を定義できました。
あとは貪欲に最大公約数を求めることになるのですが，計算時間を減らしてやるために少し工夫してやります。
３つの数 a,b,c の選び方は次の三通りあります。

1. ３つの値がすべて等しい　ex.) (3, 3, 3)
2. ２つの値が等しい ex.) (1, 1, 3)
3. どの値も等しくない ex.) (1, 2, 3)

このパターン１のとき，このような a,b,c の選び方は１通りしかありません。
パターン２のときは，このような a,b,c の選び方は上記の例だと (a,b,c) = (1,1,3), (1,3,1), (3,1,1)の３通りあります。（３C１＝３）
パターン３のときは，３！＝６通りの選び方があります。
このそれぞれについて，３つの数が同じ組み合わせなら当然最大公約数も同じ値になるので，ループの中でこの３パターンを調べ，そのパターンの数を最大公約数にかけてやればよいです。

どういうことかというと，例えば上記のパターン３の時，これは gcd(1,2,3) = 1 なのですが，これが同様にgcd(2,3,1) だとか gcd(3,1,2) だとかの同じ数の組み合わせで６通りあるので，
1 × 6 = 6
を最大公約数の和に加えてやればいいです。

このようにやってあげることで，a,b,c に a ≦ b ≦ c という条件のもとでループをかませるようになり，若干ですが計算量が減ります。

では，以下に解答例を載せておきます。

解答例

k = int(input())
 
def gcd2(a,b):
    if b == 0:
        return a
    return gcd2(b,a%b)

def gcd3(a,b,c):
    return gcd2(gcd2(a,b), c)

ans = 0
for a in range(1,k+1):
    for b in range(a,k+1):
        for c in range(b, k+1):
            if a == b == c:
                ans += gcd3(a,b,c)
            elif a == b or b == c:
                ans += gcd3(a,b,c)*3
            else:
                ans += gcd3(a,b,c)*6

print(ans)

いかがだったでしょうか。
少しみにくいコードではありますが，これで何とか制限時間以内に答えることができました。
もし何かありましたら，気軽にコメントしてくださいね！
それでは！