結果
問題 | No.1666 累乗数 |
ユーザー |
![]() |
提出日時 | 2021-09-03 22:02:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,458 bytes |
コンパイル時間 | 5,974 ms |
コンパイル使用メモリ | 250,964 KB |
最終ジャッジ日時 | 2025-01-24 05:49:09 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | TLE * 19 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 long long get(long long n,long long b){ long long ok = 1,ng = Inf; if(b>=20){ ng = 10; } else if(b>=10){ ng = 70; } while(ng-ok>1LL){ long long mid = (ok+ng)/2; long long t = n; rep(i,b){ t /= mid; } if(t==0)ng = mid; else ok = mid; } return ok; } int main(){ vector<long long> p; for(int i=2;i<60;i++){ int c = 0; for(int j=1;j<=i;j++){ if((i%j==0))c++; } if(c==2)p.push_back(i); } int m = p.size(); vector<int> mul(1<<m,0); vector<int> si(1<<m,0); for(int i=1;i<(1<<m);i++){ mul[i] = 1; si[i] = -1; rep(j,m){ if((i>>j)&1){ si[i] *= -1; mul[i] = min((long long)60,mul[i]*p[j]); } } } vector<int> mm,ss; rep(i,mul.size()){ if(si[i]!=0 && mul[i]!=60){ mm.push_back(mul[i]); ss.push_back(si[i]); } } //cout<<mm.size()<<endl; int Sum = 0; rep(i,mul.size()){ if(mul[i]==60)Sum += si[i]; } int _t; cin>>_t; rep(_,_t){ long long K; cin>>K; long long ok = 0,ng = 1000000000000000000; while(ng-ok>1LL){ long long mid = (ok+ng)/2; long long sum = 0LL; sum += Sum; rep(i,mm.size()){ sum += get(mid,mm[i])*ss[i]; } if(sum >= K)ng = mid; else ok = mid; } cout<<ok+1<<endl; } return 0; }