Divisor [第八回 アルゴリズム実技検定 D]

https://atcoder.jp/contests/past202109-open/tasks/past202109_d

前提知識

• 約数列挙

解説

https://atcoder.jp/contests/past202109-open/submissions/26602449

とある数の約数の個数が計算できれば、あとは判定するだけとなるので、
実質問題視されているのは、約数の部分である。
今回は制約的に実は約数列挙してしまっても問題ない。
今後のためにも、高速に約数列挙する方法を学んでおこう。
自分はライブラリ化してあるので、回答自体は貼るだけだった。

約数列挙

自分が下手に説明するより、
N の約数を全列挙するアルゴリズム | アルゴリズムロジック
を見る方がいいと思う。
計算量がO(sqrt(N))となっているが、sqrtは平方根のことである。
平方根を知らない学生については、そちらも学ぶといいかもしれない。

あと、自分の実装では少し計算量が悪くてlogがついてしまっているのだが、
今まで問題になったことはない。
自分の実装は上の投稿リンクからたどってほしい。

int X, Y;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> Y;

    int cntX = enumdiv(X).size();
    int cntY = enumdiv(Y).size();

    if (cntX > cntY) cout << "X" << endl;
    else if (cntX < cntY) cout << "Y" << endl;
    else cout << "Z" << endl;
}