ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Benelux Algorithm Programming Contest 2016 I Older Brother

問題

整数qが与えられたときに、なんかしらの素数pとおいて、q = p^{k}となるかどうかを調べろ、という問題です(kは1以上です)。

解法

まずはq=1の場合をコーナーケースとしてはじきます。
次に、その他の数を調べていきます。
単純に素数を1つずつみていき最後までループをしてしまうと間に合わないので、どうにかして途中でうちきる必要があります。
実は、\sqrt{q}までを見てしまえば答えがわかってしまいます。
それより大きい数を素因数にもつとき、残りの素因数はすべて\sqrt{q}未満になるからです。
ということで、mapを利用し、素因数をキーにしつつ、使った素因数の個数を記録します。素因数が見つかるたびにqからその素因数を割ってしまいましょう。
\sqrt{q}まで調べたら、今のこっているqも素因数としてカウントし、最後に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;
}