AtCoder ABC-162 C - Sum of gcd of Tuples (Easy) /
方針
3つの整数に対してユークリッドの互除法を使いました。
3重ループは時間がかかるので非推奨ですが...
#include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; #define lli long ling int; int gcd(int a, int b) { int r; r = a % b; while(r!=0) { a = b; b = r; r = a % b; } return b; } int main() { long long int K, sum = 0; scanf("%lld", &K); for (int i = 1; i <= K; i++) { for (int j = 1; j <= K; j++) { for (int k = 1; k <= K; k++) { // i,j,k gcd int a, b, c, d, tmp; a = i; b = j; c = k; if (a < b) { tmp = a; a = b; b = tmp; } d = gcd(a, b); if (c < d) { tmp = c; c = d; d = tmp; } int res = gcd(c, d); sum += res; } } } printf("%lld\n", sum); return 0; }