Official
B - 3-smooth Numbers Editorial by MMNMM
より高速な解法(この解説は少し発展的な解説です。この問題の標準的な解説より少し難しい表現があります。)
この問題は、時間・空間計算量ともに \(O(\log\log N)\) で解くことができます。
この解説 における \(a,b\) の値を求める際に指数探索を用いることでこの時間計算量が実現できます。
また、\(\dfrac N{3 ^ b}\) が \(2\) のべきであるかの判定には popcount を用いることができ、この計算も \(O(\log\log N)\) 時間で行えます。
ビット演算を用いて \(O(1)\) 時間で判定を行うこともできます(正の整数 \(x\) が \(2\) のべきであることは、!(x & x - 1)
と同値です)。
C++ では std::has_single_bit
関数が提供されているため、この部分の処理をそちらに任せることもできます。
実装例は以下のようになります。
#include <iostream>
#include <vector>
#include <bit>
using namespace std;
int main() {
unsigned long N;
cin >> N;
vector<unsigned long> pow_3{3};
for (int i = 0; i < 5 && N % pow_3[i] == 0; ++i) // ループは O(log b) 回繰り返される
pow_3.emplace_back(pow_3[i] * pow_3[i]); // 3^(2^i)^2 = 3^(2^(i+1)) を計算
while (!empty(pow_3)) {
if (N % pow_3.back() == 0) // 3^(2^i) で割れたら割る
N /= pow_3.back();
pow_3.pop_back();
}
if (has_single_bit(N)) // 残りが 2 の累乗なら Yes
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
posted:
last update: