[AtCoder] ABC 180 C – Cream puff

2020年10月17日2020年12月12日

問題

方針

人数が \( N \) の約数であるとき平等に分けることができるので、約数の列挙を行います。 \( N \bmod x = 0 \) であるとき、\( x \) は \( N \) の約数となるので、\( 1 \leq x \leq \sqrt{N}\) の範囲で全探索します。なぜ、\( x \) の上限が  \( \sqrt{N} \) であるかというと、\( \sqrt{N} + 1 \) 以上の \( N \) の約数は、

\[ \dfrac{N}{x}\]

として求めることができるからです。

コード

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

int main() {
    ll N;
    cin >> N;
    set<ll> s;
    for (ll i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            s.insert(i);
            s.insert(N / i);
        }
    }
    for (ll i : s) {
        cout << i << "\n";
    }
    return 0;
}