結果
問題 |
No.3236 累乗数大好きbot
|
ユーザー |
|
提出日時 | 2025-08-17 11:52:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,861 bytes |
コンパイル時間 | 1,284 ms |
コンパイル使用メモリ | 132,952 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-08-17 11:52:28 |
合計ジャッジ時間 | 9,579 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 WA * 3 RE * 27 |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <memory> #include <algorithm> #include <set> #include <map> #include <queue> #include <iomanip> #include <bitset> #include <string> #include <list> #include <deque> #include <stack> #include <limits> #include <atcoder/fenwicktree.hpp> #include <atcoder/segtree.hpp> #include <atcoder/modint.hpp> #include <atcoder/dsu.hpp> using namespace atcoder; using namespace std; using ll = long long; using ull = unsigned long long; template <class T> using max_heap = priority_queue<T>; template <class T> using min_heap = priority_queue<T, vector<T>, greater<>>; ll ll_min = numeric_limits<ll>::min(); ll ll_max = numeric_limits<ll>::max(); ll ALPHABET_N = 26; using mint = modint998244353; #define rep(i, n) for (ll i = (ll)0; i < (ll)n; i++) #define rep_(i, k, n) for (ll i = (ll)k; i < (ll)n; i++) #define all(a) a.begin(), a.end() struct Eratosthenes { // テーブル vector<bool> isprime; // 整数 i を割り切る最小の素数 vector<int> minfactor; // コンストラクタで篩を回す Eratosthenes(int N) : isprime(N+1, true), minfactor(N+1, -1) { // 1 は予めふるい落としておく isprime[1] = false; minfactor[1] = 1; // 篩 for (int p = 2; p <= N; ++p) { // すでに合成数であるものはスキップする if (!isprime[p]) continue; // p についての情報更新 minfactor[p] = p; // p 以外の p の倍数から素数ラベルを剥奪 for (int q = p * 2; q <= N; q += p) { // q は合成数なのでふるい落とす isprime[q] = false; // q は p で割り切れる旨を更新 if (minfactor[q] == -1) minfactor[q] = p; } } } // 高速素因数分解 // pair (素因子, 指数) の vector を返す vector<pair<int,int>> factorize(int n) { vector<pair<int,int>> res; while (n > 1) { int p = minfactor[n]; int exp = 0; // n で割り切れる限り割る while (minfactor[n] == p) { n /= p; ++exp; } res.emplace_back(p, exp); } if(n != 1) { res.emplace_back(n, 1); } return res; } }; int main() { ll q; cin>>q; Eratosthenes er(1000005); rep(_,q){ ll n; cin>>n; auto factors = er.factorize(n); if(all_of(factors.begin(), factors.end(), [&](const pair<int, int>& p) { return p.second == factors.front().second; })) { cout<<factors.front().second<<endl; } else { cout<<1<<endl; } } return 0; }