C. Product of Three Numbers (Codeforces Round #615 Div. 3)

問題

https://codeforces.com/contest/1294/problem/C

問題概要

整数nが与えられる。それを、3つの相異なる2以上の整数の積の形、つまりの形で表すことができるか答えよ。

また、できるなら一例を示せ。

考察

難しく考える必要はなく、2から順に割って確かめていけばよいです。nがaで割り切れ、がbで割り切れたとき、がcにあたります。

なお、このような算術では必須の知識ですが、試す数は最大でまででよいです。がnになりますから。この問題は三分割なのでさらに小さい数にできますが、計算量的にはで充分です。

気をつけなければならないのは、が1になったりaかbと同じ数になった場合は条件を満たせないので"NO"としなければなりません。（私はそのへんのあれこれで通算4WAも出してしまいました。ああ・・・。）

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> ans;
        bool ok = false;
        for (int i = 2; i < (int)sqrt(n) + 1; i++) {
            if (n % i == 0) {
                n /= i;
                ans.emplace_back(i);
                if (ans.size() == 2) {
                    if (i != n && ans[0] != n && n != 1) {
                        ok = true;
                        cout << "YES" << endl;
                        cout << ans[0] << " " << ans[1] << " " << n << endl;
                    }
                    break;
                }
            }
        }
        if (!ok) cout << "NO" << endl;
    }
}

余談

ちなみに、私が最初に思いついた解法は、素因数分解して場合分けを頑張るというものでしたが、場合分けでうっかりミスしそうだったので止めました。Twitterを見ていると、そっちで解いた人も結構いたようですね。

結果論ではありますが、私もそっちにしたほうがまだましだったような気がします・・・。