結果
問題 |
No.2379 Burnside's Theorem
|
ユーザー |
|
提出日時 | 2025-02-05 19:37:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 1,402 bytes |
コンパイル時間 | 2,691 ms |
コンパイル使用メモリ | 164,148 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-02-05 19:37:55 |
合計ジャッジ時間 | 4,626 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define forn(i, a, n) for (int i = a; i < n; i++) #define all(ans) ans.begin(), ans.end() const ll MAXN = 1e6; // Limit for sieve vector<bool> prime(MAXN + 1, true); vector<ll> primes; void sieve() { prime[0] = prime[1] = false; // 0 and 1 are not primes for (ll p = 2; p * p <= MAXN; p++) { if (prime[p]) { primes.pb(p); for (ll i = p * p; i <= MAXN; i += p) prime[i] = false; } } // Collect remaining prime numbers for (ll p = sqrt(MAXN) + 1; p <= MAXN; p++) { if (prime[p]) primes.pb(p); } } void solve() { ll n; cin >> n; int cnt = 0; // Count of distinct prime factors for (ll p : primes) { if (p * p > n) break; // No need to check beyond sqrt(n) if (n % p == 0) { cnt++; // Found a prime factor while (n % p == 0) { n /= p; } } } // If `n > 1`, then `n` itself is a prime factor if (n > 1) cnt++; cout << (cnt <= 2 ? "Yes\n" : "No\n"); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); sieve(); // Precompute primes once int tc = 1; // cin >> tc; // Uncomment for multiple test cases while (tc--) { solve(); } return 0; }