結果
問題 | No.1666 累乗数 |
ユーザー |
![]() |
提出日時 | 2021-09-02 06:11:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 615 ms / 2,000 ms |
コード長 | 1,047 bytes |
コンパイル時間 | 1,979 ms |
コンパイル使用メモリ | 180,000 KB |
実行使用メモリ | 113,536 KB |
最終ジャッジ日時 | 2024-12-15 09:05:08 |
合計ジャッジ時間 | 15,383 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 19 |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll exp(ll n,ll r){if(r==0)return 1;return n*exp(n,r-1);} int main(){ set<ll>st; set<ll>unuse; for(ll i=1;i<=1000;i++)unuse.insert(i*i); for(ll i=2;i<=((ll)1e6)+10;i++){ if(unuse.count(i))continue; for(ll j=3;;j+=2){ if(pow(i,j)<=((ll)1e18)+10)st.insert(exp(i,j)); else break; } } map<ll,ll>mp; ll cur=0; for(auto x:st){ mp[x]=++cur; } ll ma=*rbegin(st); auto cnt=[&](ll n)->ll{ ll ok=0; ll ng=((ll)1e9)+10; while(ng-ok>1){ ll mid=(ok+ng)/2; if(mid*mid<=n)ok=mid; else ng=mid; } if(n>=ma)return st.size()+ok; else return mp[(*st.lower_bound(n+1))]-1+ok; }; ll t;cin>>t; while(t--){ ll m;cin>>m; ll ok=1e18,ng=-1; while(ok-ng>1){ ll mid=(ok+ng)/2; if(cnt(mid)>=m)ok=mid; else ng=mid; } cout<<ok<<endl; } }