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

zuka

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

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

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

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC180-C「Cream puff」です。

ポイント

約数を数え上げる問題です。注意すべき点は，全ての$N$に対して約数を調べてしまうと計算が間に合わないため，約数をペアで見つけていくことで$O(\lfloor \sqrt{N} \rfloor)$で済むという点です。調べ上げた約数はそのまま表示すると小さい順に出力されないため，配列を使って管理しておくと良いでしょう。

ただし，ここで引っ掛けがあります。配列に約数を突っ込んでいくと，$N$が平方数のときに同じ約数が2回カウントされてしまいます。そこで，重複を避けながらデフォルトでソートをしてくれるsetを使うと楽に数え上げた約数を管理できます。

setへの要素追加はinsert，要素アクセスは範囲for文を利用すると良いでしょう。また，B問題同様入力のオーバーフローに注意してください。

実装

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

ll N;
set<ll> ANS;

int main(){
  cin >> N;
  repi(i, 1, ll(sqrt(N))+1){
    if (N % i == 0){
      ANS.insert(i);
      ANS.insert(N/i);
    }
  }
  for (auto ans : ANS) cout << ans << endl;
}