素直に for 文を回して全部足せば OK！！！
なお、3 つの整数の最大公約数の求め方に注意。

問題概要

$1 \le a, b, c \le K$ を満たすすべての整数 $a, b, c$ の組に対しての、

${\rm GCD}(a, b, c)$

の総和を求めよ。

制約

$1 \le K \le 200$

考えたこと

素直に $O(K^{3})$ 通りの組について、GCD を求めて合計しても間に合う。なお、3 つの整数の最大公約数について、以下の式が成り立つ

${\rm GCD}(a, b, c) = {\rm GCD}({\rm GCD}(a, b), c)$

つまり、

$a, b$ の最大公約数を求めて、それを $d$ として、
$d, c$ の最大公約数を求める

というようにすれば OK。一回一回の最大公約数の計算には $O(\log{K})$ の計算量がかかるので、全体の計算量は $O(K^{3}\log{K})$ となる。

#include <bits/stdc++.h>
using namespace std;

long long GCD(long long x, long long y) {
    if (y == 0) return x;
    else return GCD(y, x % y);
}

int main() {
    int K;
    cin >> K;
    long long res = 0;
    for (int a = 1; a <= K; ++a) {
        for (int b = 1; b <= K; ++b) {
            for (int c = 1; c <= K; ++c) {
                res += GCD(GCD(a, b), c);
            }
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 162 C - Sum of gcd of Tuples (Easy) (灰色, 300 点)

問題概要

制約

考えたこと