SRM517 Div1 Easy - CompositeSmash

問題

　整数をそれぞれ2以上である数字の積に分解する操作が行える。分解して得られる整数はランダムであるとするとき、整数を作ることができるかどうか判定せよ。

解法

　気合を入れて場合分けをする。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class CompositeSmash {
public:
    string thePossible(int N, int target) {
        if (N % target != 0) {
            return "No";
        }
        if (N == target) {
            return "Yes";
        }
        auto target_factor = primeFactorization(target);
        if (target_factor.size() != 1) {
            return "No";
        }
        auto top = target_factor.front();
        if (top.second == 1) {
            //targetは素数
            return "Yes";
        } else if (top.second == 2) {
            //Nもtop.firstの累乗ならYes
            auto N_factor = primeFactorization(N);
            if (N_factor.size() == 1 && N_factor.front().first == top.first) {
                return "Yes";
            } else {
                return "No";
            }
        } else {
            return "No";
        }
    }
private:
    vector<pair<ll, ll>> primeFactorization(ll n) {
        vector<pair<ll, ll>> result;
        for (ll i = 2; i * i <= n; i++) {
            ll num = 0;
            while (n % i == 0) {
                n /= i;
                num++;
            }
            if (num != 0) {
                result.push_back({ i, num });
            }
        }

        if (n != 1) {
            result.push_back({ n, 1 });
        }

        return result;
    }
};