結果

問題 No.3236 累乗数大好きbot
ユーザー ルビサファせだい
提出日時 2025-08-17 12:20:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,090 ms / 4,000 ms
コード長 1,481 bytes
コンパイル時間 1,918 ms
コンパイル使用メモリ 204,644 KB
実行使用メモリ 88,996 KB
最終ジャッジ日時 2025-08-17 12:21:32
合計ジャッジ時間 36,417 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>

#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()

bool will_multiply_overflow(ll a, ll b)
{
    if (a == 0 || b == 0) return false;
    if (a > 0 && b > 0) return a > ll_max / b;
    if (a < 0 && b < 0) return a < ll_max / b;
    if (a > 0 && b < 0) return b < ll_min / a;
    if (a < 0 && b > 0) return a < ll_min / b;
    return false;
}

int main()
{
    ll q;
    cin >> q;
    unordered_map<ll, ll> mp;
    for(ll i = 2; i <= 1000000; i++) {
        ll x = i;
        ll iter = 1;
        while(1000000000000LL >= x) {
            mp[x] = max(mp[x], iter);
            if(will_multiply_overflow(x, i)) break;
            x *= i;
            iter++;
        }
    }

    rep(_, q)
    {
        ll n;
        cin >> n;
        if (mp.find(n) != mp.end()) {
            cout << mp[n] << endl;
        } else {
            cout << 1 << endl;
        }
    }
    return 0;
}
0