SRM 517 div1 easy:CompositeSmash

SRM 517の練習会に参加しました。ゼロ完で悲しみが募る。

問題

TopCoder Statistics - Problem Statement

解法

基本的にtargetがNの素因数ならOKです。ただ,例外として,
・targetがNと同じならOK
・Nがひとつの素因数pのみを持ちかつNがp*p以上の場合は,p*pもOK
に注意です。2つめ忘れました。

const int MAXN = 100100;
int prime[MAXN];

class CompositeSmash {
public:
    string thePossible(int N, int target) {
        int n = N;
        for (int i = 2; i < MAXN; i++) {
            if (prime[i] == 0) {
                for (int j = 2; i*j < MAXN; j++) {
                    prime[i*j] = i;
                }
            }
        }
        if (N == target) return "Yes";
        set<int> P;
        while (prime[N]) {
            P.insert(prime[N]);
            N /= prime[N];
        }
        if (N != 1) P.insert(N);
        if (P.find(target) != P.end()) return "Yes";
        else {
            if (P.size() == 1) {
                int cnt = 0;
                while (n > 1) {
                    cnt++;
                    n /= N;
                }
                if (cnt >= 2 && target == N*N)
                    return "Yes";
            }
            return "No";
        }
    }
};