結果
問題 | No.2379 Burnside's Theorem |
ユーザー |
|
提出日時 | 2023-07-14 21:29:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 156 ms / 2,000 ms |
コード長 | 1,512 bytes |
コンパイル時間 | 1,743 ms |
コンパイル使用メモリ | 142,620 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-16 06:18:38 |
合計ジャッジ時間 | 6,134 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#include <deque>#include <queue>#include <set>#include <map>#include <limits>#include <cmath>#include <iomanip>#include <functional>#include <random>#include <set>#include <atcoder/string>#include <atcoder/math>#include <unordered_map>#include <climits>using namespace std;using ll = long long;using namespace atcoder;vector<ll> prime_numbers(ll n){if (n <= 1){return vector<ll>(0);}vector<ll> ans = {2};for(ll i = 3;i <= n;i++){bool is_prime = true;for(ll j = 0; ans[j] * ans[j] <= i;j++){if (i % ans[j] == 0){is_prime = false;break;}}if (is_prime){ans.push_back(i);}}return ans;}vector<ll> primes = prime_numbers(1000001);void decomposite(ll N, map<ll,ll> &factors,ll p_index = 0){if (N == 1){return;}while (primes[p_index] * primes[p_index] <= N ) {if (N % primes[p_index] == 0) {factors[primes[p_index]] += 1;decomposite(N/primes[p_index],factors,p_index);return;} else {p_index++;}}factors[N] += 1;}int solve(){ll N;cin >> N;map<ll,ll> dec;decomposite(N,dec);if (dec.size() <= 2){cout << "Yes\n";}else{cout << "No\n";}return 0;}int main(){// ll T;// cin >> T;// while(T--){solve();// }return 0;}