#386464 (C++14) No.897 compαctree

• 問題: No.897 compαctree
• ユーザー: pazzle1230
• 提出日時: 2019-10-04 21:23:11
• 言語: C++14 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 5,363 bytes
• コンパイル時間: 1,534 ms
• コンパイル使用メモリ: 164,132 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-04-14 10:03:53
• 合計ジャッジ時間: 2,302 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,940 KB
testcase_05	AC	1 ms; 6,940 KB
testcase_06	AC	2 ms; 6,940 KB
testcase_07	AC	2 ms; 6,944 KB
testcase_08	AC	2 ms; 6,940 KB
testcase_09	AC	2 ms; 6,944 KB
testcase_10	AC	2 ms; 6,940 KB
testcase_11	AC	2 ms; 6,940 KB
testcase_12	AC	2 ms; 6,940 KB
testcase_13	AC	2 ms; 6,940 KB

ソースコード

#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;
        if (K == 1) {
            cout << N-1 << endl;
            continue;
        }
        while (N) {
            res++;
            N = (N+K-2) / K;
        }
        cout << res-1 << endl;
    }
}