結果
問題 |
No.1666 累乗数
|
ユーザー |
👑 |
提出日時 | 2022-08-28 11:41:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 178 ms / 2,000 ms |
コード長 | 1,364 bytes |
コンパイル時間 | 1,166 ms |
コンパイル使用メモリ | 97,712 KB |
最終ジャッジ日時 | 2025-02-06 22:09:58 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 19 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main(){ vector<long long> A; for(long long i = 2; 1000000 > i; i++){ long long nw = i*i; while(1000000000000000000/i >= nw){ nw *= i; if((long long)sqrt(nw) * (long long)sqrt(nw) == nw)continue; A.push_back(nw); } } sort(A.begin(),A.end()); A.erase(unique(A.begin(),A.end()),A.end()); int t;cin>>t; for(int i = 0; t > i; i++){ long long x;cin>>x; long long mn = 0; long long mx = A.size()+1; while(mx-mn > 1){ long long ce = (mx+mn)/2; long long ele; if(ce == 0){ ele = 0; }else if(ce == A.size()){ ele = 1000000000+ce-1; }else{ ele = ce+(long long)sqrt(A[ce-1]); } if(ele <= x){ mn = ce; }else{ mx = ce; } } //cout << mn << endl; if(mn && mn+(long long)sqrt(A[mn-1]) == x){ //cout << "!!" << endl; cout << A[mn-1] << endl; }else{ long long diff = x-(mn+(long long)sqrt(A[mn-1])); long long re = sqrt(A[mn-1])+diff; cout << re*re << endl; } } }