結果
問題 | 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 secondusing 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>::typefill_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>::typefill_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-bitfor (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-bitfor (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;}}