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

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

問題概要

を満たすすべての整数 の組に対しての、

• 

の総和を求めよ。

制約

• 

考えたこと

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

• 

つまり、

• の最大公約数を求めて、それを として、
• の最大公約数を求める

というようにすれば OK。一回一回の最大公約数の計算には の計算量がかかるので、全体の計算量は となる。

#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;
}