ABC162

昨日のコンテストについて。C#はまだ慣れないず(エラー出まくる)、レートが下がるのも嫌なので、今回はC++で挑戦。

結論から言うと、ボロボロでした。C問題でつまずいた。

途中までなぜか最小公倍数をひたすら求めたり、3つの数の最大公約数の求め方をぐだぐだ考えたり、計算量が間に合わずTLEになりまくったりで大荒れ(O(K^4)とかやってた)。

シンプルに3つの数a,b,cの最大公約数gcd(a,b,c)は、まず2数の最大公約数gcd(a,b)を求め、gcd(a,b)と残りの1つcの最大公約数を求めればいい。要するにgcd(gcd(a,b),c)で求まる。gcd(a,b)はユークリッドの互除法を使って求める。

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

//2数の最大公約数
int gcd(int x, int y){
 if(x % y == 0) return y;
 return gcd(y, x % y);
}

//3数の最大公約数
int gcd_3(int x, int y, int z){
 return gcd(gcd(x,y),z);
}

int main() {
 
 int k; cin >> k;
 
 int ans = 0;
 for(int a=1; a<=k; a++){
   for(int b=a; b<=k; b++){
     for(int c=b; c<=k; c++){
       
       //何とか計算量を減らそうとしてあがいた残り
       if(a==b && b==c) ans += gcd_3(a,b,c);
       else if(a != b && b != c) ans += 6 * gcd_3(a,b,c);
       else ans += 3 * gcd_3(a,b,c);
       
     }
   }
 }
 
 cout << ans << endl;
}

以上！