結果

問題 No.3236 累乗数大好きbot
コンテスト
ユーザー D M
提出日時 2025-09-26 13:28:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,572 ms / 4,000 ms
コード長 1,288 bytes
コンパイル時間 2,991 ms
コンパイル使用メモリ 275,808 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-26 13:30:23
合計ジャッジ時間 87,084 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// a^k <= n ? を __int128 で安全に判定
static inline bool leq_pow(ll a, int k, ll n){
  __int128 p = 1;
  for(int i=0;i<k;i++){
    p *= a;
    if(p > (__int128)n) return false;
  }
  return true;
}

// floor(n^{1/k}) を二分探索で求める
static inline ll kth_root_floor(ll n, int k){
  ll lo = 1, hi = n;             // 上限を n にしても log2(n) ≈ 60 回で収束
  while(lo < hi){
    ll mid = (lo + hi + 1) >> 1; // 上側に寄せる
    if(leq_pow(mid, k, n)) lo = mid;
    else hi = mid - 1;
  }
  return lo;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int q; cin >> q;
  while(q--){
    long long n; cin >> n;
    if(n == 1){                   // 1 は任意の指数で 1^k = 1 だが、仕様を合わせて 1 を返す
      cout << 1 << '\n';
      continue;
    }

    int ans = 1;
    for(int k = 60; k >= 2; --k){ // 64bit なら 2^60 > 1e18 なので 60 で十分
      ll r = kth_root_floor(n, k);
      // ちょうど r^k == n かを確認
      __int128 p = 1;
      for(int i=0;i<k;i++){
        p *= r;
        if(p > (__int128)n) break;
      }
      if(p == (__int128)n){
        ans = k;
        break;
      }
    }
    cout << ans << '\n';
  }
}
0