結果
問題 | No.897 compαctree |
ユーザー |
![]() |
提出日時 | 2019-10-04 21:22:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,276 bytes |
コンパイル時間 | 1,522 ms |
コンパイル使用メモリ | 167,876 KB |
実行使用メモリ | 13,640 KB |
最終ジャッジ日時 | 2024-10-03 07:01:14 |
合計ジャッジ時間 | 4,996 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 TLE * 1 -- * 2 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define INF_LL (int64)1e18 #define INF (int32)1e9 #define REP(i, n) for(int64 i = 0;i < (n);i++) #define FOR(i, a, b) for(int64 i = (a);i < (b);i++) #define all(x) x.begin(),x.end() #define fs first #define sc second using int32 = int_fast32_t; using uint32 = uint_fast32_t; using int64 = int_fast64_t; using uint64 = uint_fast64_t; using PII = pair<int32, int32>; using PLL = pair<int64, int64>; const double eps = 1e-10; template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;} template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;} template<typename T> vector<T> make_v(size_t a){return vector<T>(a);} template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts){ return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename U,typename... V> typename enable_if<is_same<T, U>::value!=0>::type fill_v(U &u,const V... v){u=U(v...);} template<typename T,typename U,typename... V> typename enable_if<is_same<T, U>::value==0>::type fill_v(U &u,const V... v){ for(auto &e:u) fill_v<T>(e,v...); } class FFT { public: using Real = double; using Complex = std::complex<double>; using size_type = std::size_t; private: static Complex mul(const Complex& a, const Complex& b) { return Complex(real(a)*real(b)-imag(a)*imag(b), real(a)*imag(b)+real(b)*imag(a)); } static void fft(std::vector<Complex> &a, bool inv = false) { std::int64_t n = a.size(); std::vector<Complex> tmp(n); std::int64_t mask = n - 1; std::int64_t h_bit = n >> 1; // highest-bit for (std::int64_t k = 1, l = mask; l > 0; k++, l >>= 1) { Complex e = std::polar(1.0, 2 * M_PI / (1 << k) * (inv ? -1 : 1)); Complex zeta =1; for (std::int64_t i = 0; i <= mask; i++) { std::int64_t idx = ((i >> k) << (k - 1)) | (i & ((1 << (k - 1)) - 1)); tmp[i] = a[idx] + mul(zeta, a[h_bit | idx]); zeta = mul(zeta, e); } std::swap(a, tmp); } if (inv) { for (std::int64_t i = 0; i < n; i++) { a[i] /= n; } } } public: static std::vector<std::int64_t> conv(const std::vector<std::int64_t>& ar, const std::vector<std::int64_t>& br) { size_type deg = ar.size() + br.size() - 1; size_type n = 1; while (n < deg) n <<= 1; std::vector<Complex> a(n, 0); for (std::int64_t i = 0; i < ar.size(); i++) a[i].real(ar[i]); for (std::int64_t i = 0; i < br.size(); i++) a[i].imag(br[i]); std::vector<Complex> c(n); fft(a); for (std::int64_t i = 0; i < n; i++) { c[i] = mul(mul(a[i] + conj(a[(n - i)%n]), a[i] - conj(a[(n - i)%n])), Complex(0, -0.25)); } fft(c, 1); std::vector<std::int64_t> cr(n); for (std::int64_t i = 0; i < deg; i++) { cr[i] = std::round(c[i].real()); } return cr; } }; namespace ArbitraryModFFT { using Real = double; using Complex = std::complex<double>; using size_type = std::size_t; static Complex mul(const Complex& a, const Complex& b) { return Complex(real(a)*real(b)-imag(a)*imag(b), real(a)*imag(b)+real(b)*imag(a)); } static void fft(std::vector<Complex> &a, bool inv = false) { std::int64_t n = a.size(); std::vector<Complex> tmp(n); std::int64_t mask = n - 1; std::int64_t h_bit = n >> 1; // highest-bit for (std::int64_t k = 1, l = mask; l > 0; k++, l >>= 1) { double deg = 2 * M_PI / (1 << k) * (inv ? -1 : 1); Complex e = Complex(cosl(deg), sinl(deg)); Complex zeta =1; for (std::int64_t i = 0; i <= mask; i++) { std::int64_t idx = ((i >> k) << (k - 1)) | (i & ((1 << (k - 1)) - 1)); tmp[i] = a[idx] + mul(zeta, a[h_bit | idx]); zeta = mul(zeta, e); } std::swap(a, tmp); } if (inv) { for (std::int64_t i = 0; i < n; i++) { a[i] /= n; } } } static std::vector<std::int64_t> conv(const std::vector<std::int64_t>& ar, const std::vector<std::int64_t>& br) { size_type deg = ar.size() + br.size() - 1; size_type n = 1; while (n < deg) n <<= 1; std::vector<Complex> a(n, 0); for (std::int64_t i = 0; i < ar.size(); i++) a[i].real(ar[i]); for (std::int64_t i = 0; i < br.size(); i++) a[i].imag(br[i]); std::vector<Complex> c(n); fft(a); for (std::int64_t i = 0; i < n; i++) { c[i] = mul(mul(a[i] + conj(a[(n - i)%n]), a[i] - conj(a[(n - i)%n])), Complex(0, -0.25)); } fft(c, 1); std::vector<std::int64_t> cr(n); for (std::int64_t i = 0; i < deg; i++) { cr[i] = std::round(c[i].real()); } return cr; } } int main(void){ int64 Q; cin >> Q; REP(_, Q) { int64 N, K; cin >> N >> K; int64 res = 0; while (N) { res++; N = (N+K-2) / K; } cout << res-1 << endl; } }