【競プロ精進ログ】ABC162-C

zuka

ABCをコツコツ解いていきます。

本記事は,管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために,積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や,なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

目次

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest(通称ABC)を解いていくものです。今回はABC162-C「Sum of gcd of Tuples (Easy)」です。

ポイント

計算量の見積もりが大切な問題でした。求めるべき値は以下の$S$です。

\begin{align}
S &= \sum_{a=1}^{K} \sum_{b=1}^{K} \sum_{c=1}^{K} \operatorname{gcd}(a, b, c)
\end{align}

まず,$1 \leq K \leq 200$であることから,gcdの計算量を無視すると$S$を求めるためには$O(K^3)=O(4\cdot 10^6)$かかります。$O(N)$は$10^8$程度の計算を約1[s]で行うことができますので,まだセーフです。

スクロールできます
$N$$O(1)$$O(\log N)$$O(N)$$O(N \log N)$$O(N^2)$$O(2^N)$
$1$一瞬一瞬一瞬一瞬一瞬一瞬
$10$一瞬一瞬一瞬一瞬一瞬一瞬
$10^3$一瞬一瞬一瞬一瞬$\fallingdotseq 0.01$[s]地球爆発
$10^6$一瞬一瞬$\fallingdotseq 0.01$[s]$\fallingdotseq 0.2$[s]$\fallingdotseq 3$[h]地球爆発
$10^8$一瞬一瞬$\fallingdotseq 1$[s]$\fallingdotseq 30$[s]$\fallingdotseq 3$[y]地球爆発
$10^{16}$一瞬一瞬$\fallingdotseq 3$[y]$\fallingdotseq 170$[y]地球爆発地球爆発
APG4b「2.06.計算量」より
表中の[s]は秒,[h]は時間,[y]は年を表す

ここで,gcdの計算量が$O(\log K)$であればまだ間に合いそうです。実際に,ユークリッドの互除法を利用すれば,$O(\log K)$の計算量で最大公約数を求めることができます。ユークリッドの互除法に関しては,以下の記事をご覧ください。

おさえるべき内容

 計算量の見積もりと各オーダの限界

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

// ユークリッドの互除法を利用した最大公約数の計算
ll gcd(ll a, ll b) {
  return b != 0 ? gcd(b, a % b) : a;
}

int main(){
  int K;
  ll sums = 0;
  cin >> K;
  // 全探索できる
  rep(i, K){
    rep(j, K){
      rep(k, K){
        sums += gcd(gcd((i+1), (j+1)), (k+1));
      }
    }
  }
  cout << sums << endl;
}
よかったらシェアしてね!

コメント

コメントする

目次
閉じる