結果
問題 |
No.3236 累乗数大好きbot
|
ユーザー |
|
提出日時 | 2025-08-15 22:56:12 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 548 ms / 4,000 ms |
コード長 | 1,259 bytes |
コンパイル時間 | 2,919 ms |
コンパイル使用メモリ | 275,704 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-15 22:56:29 |
合計ジャッジ時間 | 16,629 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
#include<bits/stdc++.h> using namespace std; long long power(long long a, int k, long long n) { long long res = 1; for (int i = 0; i < k; ++i) { if (a == 0) return 0; if (res > n / a) { return n + 1; } res *= a; } return res; } long long integer_kth_root(long long n, int k) { if (n <= 1) return n; if (k == 1) return n; if (k >= 63) return 1; long long low = 1, high = n; long long ans = 1; while (low <= high) { long long mid = low + (high - low) / 2; if (mid == 0) { low = 1; continue; } long long p = power(mid, k, n); if (p <= n) { ans = mid; low = mid + 1; } else { high = mid - 1; } } return ans; } int main(){ int q; cin>>q; while(q--){ long n; cin>>n; int ans=-1; for(int a=2;a<=100;a++){ long now=1; int c=0; while(now<n){ now*=a; c++; if(now==n){ ans=c; break; } if(now>=n)break; } if(ans!=-1)break; } if(ans!=-1){ cout<<ans<<'\n'; continue; } for(int k=5;k>=1;k--){ long x=integer_kth_root(n,k); if(power(x,k,n)==n){ cout<<k<<'\n'; break; } } } }