Benelux Algorithm Programming Contest 2016 I Older Brother
問題
整数が与えられたときに、なんかしらの素数をとおいて、となるかどうかを調べろ、という問題です(は1以上です)。
解法
まずは=1の場合をコーナーケースとしてはじきます。
次に、その他の数を調べていきます。
単純に素数を1つずつみていき最後までループをしてしまうと間に合わないので、どうにかして途中でうちきる必要があります。
実は、までを見てしまえば答えがわかってしまいます。
それより大きい数を素因数にもつとき、残りの素因数はすべて未満になるからです。
ということで、mapを利用し、素因数をキーにしつつ、使った素因数の個数を記録します。素因数が見つかるたびにからその素因数を割ってしまいましょう。
まで調べたら、今のこっているも素因数としてカウントし、最後にmapのサイズが1であれば条件を満たす、そうでなければ条件を満たしていない、と判定して答えを出力したら終わりになります。
提出コードは以下になります。
#include <bits/stdc++.h> #define N 1000000000 using namespace std; void prians(bool answer) { if(answer) cout << "yes" << endl; else cout << "no" << endl; } int q; map<int, int> mp; bool solve(); int main() { cin >> q; prians(solve()); return 0; } bool solve() { int i = 2; if(q == 1) return 0; while(q != 1 && i * i <= q) { while(q % i == 0) { q /= i; ++mp[i]; } ++i; } if(q != 1) ++mp[q]; return mp.size() == 1; }