結果
問題 |
No.3236 累乗数大好きbot
|
ユーザー |
|
提出日時 | 2025-08-17 11:54:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,852 bytes |
コンパイル時間 | 1,179 ms |
コンパイル使用メモリ | 133,160 KB |
実行使用メモリ | 11,308 KB |
最終ジャッジ日時 | 2025-08-17 11:54:53 |
合計ジャッジ時間 | 7,831 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | RE * 31 |
ソースコード
#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<ll> minfactor; // コンストラクタで篩を回す Eratosthenes(ll N) : isprime(N+1, true), minfactor(N+1, -1) { // 1 は予めふるい落としておく isprime[1] = false; minfactor[1] = 1; // 篩 for (ll p = 2; p <= N; ++p) { // すでに合成数であるものはスキップする if (!isprime[p]) continue; // p についての情報更新 minfactor[p] = p; // p 以外の p の倍数から素数ラベルを剥奪 for (ll q = p * 2; q <= N; q += p) { // q は合成数なのでふるい落とす isprime[q] = false; // q は p で割り切れる旨を更新 if (minfactor[q] == -1) minfactor[q] = p; } } } // 高速素因数分解 // pair (素因子, 指数) の vector を返す vector<pair<ll,ll>> factorize(ll n) { vector<pair<ll,ll>> res; while (n > 1) { ll p = minfactor[n]; ll 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(1000005LL); 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; }