AtCoder Beginner Contest 162 C

2020年4月28日

AtCoder Beginner Contest 162 C を Python で

引き続き,AtCoder Beginner Contest 162 C を Python で解説していきたいと思います。
今回はなかなかジャッジが遅かったようで,この問題十分くらいジャッジが出ずになかなか焦りました。(-_-;)
gcd の処理もちょっと抜けていて手がすぐには動かなかったので,それも反省です。
それではもう早速解説に進みます。
まずは問題文から。
https://atcoder.jp/contests/abc162/tasks/abc162_c
(まだ慣れておらず,Σ記号の表示がうまくいかないみたいです。数日中に直しますので,問題文は atcoder の実際の問題文のページを参照してもらえれば分かりやすいと思います。)


C – Sum of gcd of Tuples (Easy)


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

配点 : 300 点

問題文

\(\sum_{a=1}^K\sum_{b=1}^K\sum_{c=1}^K gcd(a,b,c)\) を求めてください。

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

制約

  • 1≤K≤200
  • K は整数

入力

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

K

出力

\(\sum_{a=1}^K\sum_{b=1}^K\sum_{c=1}^K gcd(a,b,c)\) の値を出力せよ。


入力例 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


解説

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

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

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

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

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

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

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

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

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

どういうことかというと,例えば上記のパターン3の時,これは gcd(1,2,3) = 1 なのですが,これが同様にgcd(2,3,1) だとか gcd(3,1,2) だとかの同じ数の組み合わせで6通りあるので,
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)

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

他の問題も解説しているので,ぜひご覧ください。
ABC 162 A
ABC 162 B
ABC 162 C
ABC 162 D
ABC 162 E
ABC 162 F