結果
問題 |
No.2751 429-like Number
|
ユーザー |
![]() |
提出日時 | 2024-05-17 10:54:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,147 ms / 4,000 ms |
コード長 | 925 bytes |
コンパイル時間 | 2,196 ms |
コンパイル使用メモリ | 196,964 KB |
最終ジャッジ日時 | 2025-02-21 14:23:04 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const int INF = 1e9 + 10; const ll INFL = 4e18; int main() { const int MX = 100000; vector<bool> is_prime(MX + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= MX; ++i) { if (is_prime[i]) { for (int j = i * i; j <= MX; j += i) { is_prime[j] = false; } } } vector<int> primes; for (int i = 2; i <= MX; ++i) { if (is_prime[i]) primes.push_back(i); } int Q; cin >> Q; while (Q--) { ll N; cin >> N; int cnt = 0; for (ll x : primes) { while (N % x == 0) { N /= x; cnt++; } if (cnt > 3) break; if (N == 1) break; } cout << ((cnt == 3 && N == 1) || (cnt == 2 && N > 1) ? "Yes" : "No") << '\n'; } }