#384762 (C++17) No.894 二種類のバス

提出ソース

結果

問題	No.894 二種類のバス
ユーザー	MiyanagaTeru
提出日時	2019-09-28 00:13:05
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 1,000 ms
コード長	10,704 bytes
コンパイル時間	3,055 ms
コンパイル使用メモリ	235,444 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-25 03:17:45
合計ジャッジ時間	3,725 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

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

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
//#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
const int64 INF = 1LL << 58;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

//intのmodを勝手に取ってくれる
template<unsigned P> struct ModInt {
    using M = ModInt;
    unsigned v;
    ModInt() : v(0) {}
    template<class Z> ModInt(Z x) : v(x >= 0 ? x % P : -x % P ? P - -x % P : 0) {}
    constexpr ModInt(unsigned v, int) : v(v) {}
    static constexpr unsigned p() { return P; }
    M operator+() const { return *this; }
    M operator-() const { return {v ? P - v : 0, 0}; }
    explicit operator bool() const noexcept { return v; }
    bool operator!() const noexcept { return !(bool) *this; }
    M operator*(M r) const { return M(*this) *= r; }
    M operator/(M r) const { return M(*this) /= r; }
    M operator+(M r) const { return M(*this) += r; }
    M operator-(M r) const { return M(*this) -= r; }
    bool operator==(M r) const { return v == r.v; }
    bool operator!=(M r) const { return !(*this == r); }
    M& operator*=(M r) { v = (uint64_t) v * r.v % P; return *this; }
    M& operator/=(M r) { return *this *= r.inv(); }
    M& operator+=(M r) { v = r.v < P - v ? v + r.v : v - (P - r.v); return *this; }
    M& operator-=(M r) { v = r.v <= v ? v - r.v : v + (P - r.v); return *this; }
    M inv() const {
        int a = v, b = P, x = 1, u = 0;
        while (b) {
        int q = a / b;
        swap(a -= q * b, b);
        swap(x -= q * u, u);
        }
        assert(a == 1);
        return x;
    }
    template<class Z> M pow(Z n) const {
        n = n >= 0 ? n % (P - 1) : P - 1 - -n % (P - 1);
        M res = 1;
        for (M a = *this; n; a *= a, n >>= 1) if (n & 1) res *= a;
        return res;
    }
    template<class Z> friend M operator*(Z l, M r) { return M(l) *= r; }
    template<class Z> friend M operator/(Z l, M r) { return M(l) /= r; }
    template<class Z> friend M operator+(Z l, M r) { return M(l) += r; }
    template<class Z> friend M operator-(Z l, M r) { return M(l) -= r; }
    friend ostream& operator<<(ostream& os, M r) { return os << r.v; }
    friend istream& operator>>(istream& is, M& r) { lint x; is >> x; r = x; return is; }
    template<class Z> friend bool operator==(Z l, M r) { return M(l) == r; }
    template<class Z> friend bool operator!=(Z l, M r) { return !(l == r); }
};

template<unsigned P, unsigned g> void dft(V< ModInt<P> >& a, bool inv = false) {
    int n = a.size();
    int j = 0;
    for (int i = 1; i < n; ++i) {
        int k = n >> 1;
        while (j >= k) j -= k, k >>= 1;
        j += k;
        if (i < j) swap(a[i], a[j]);
    }
    assert((P - 1) % n == 0);
    auto zeta = ModInt<P>(g).pow((P - 1) / n);
    if (inv) zeta = zeta.inv();
    V< ModInt<P> > xi(n + 1, 1);
    for (int i = 0; i < n; ++i) xi[i + 1] = xi[i] * zeta;
    for (int k = 1; k < n; k <<= 1) {
        for (int i0 = 0; i0 < n; i0 += k << 1) {
            for (int i = i0; i < i0 + k; ++i) {
                j = i + k;
                a[j] *= xi[(n >> 1) / k * (i - i0)];
                tie(a[i], a[j]) = make_pair(a[i] + a[j], a[i] - a[j]);
            }
        }
    }
}

template<unsigned P, unsigned g = 3> void convolution(V< ModInt<P> >& a, V< ModInt<P> >& b) {
    assert(!a.empty() and !b.empty());
    int n = 1 << __lg(2 * (a.size() + b.size() - 1) - 1);
    a.resize(n), b.resize(n);
    dft<P, g>(a), dft<P, g>(b);
    for (int i = 0; i < n; ++i) a[i] *= b[i];
    dft<P, g>(a, true);
    auto inv_n = ModInt<P>(n).inv();
    for (int i = 0; i < n; ++i) a[i] *= inv_n;
}

void convolution(V<lint>& a, V<lint>& b) {
    using Mint0 = ModInt<998244353>;
    using Mint1 = ModInt<1004535809>;
    int n = a.size(), m = b.size();
    V<Mint0> a0(n), b0(m);
    V<Mint1> a1(n), b1(m);
    for (int i = 0; i < n; ++i) a0[i] = a[i], a1[i] = a[i];
    for (int j = 0; j < m; ++j) b0[j] = b[j], b1[j] = b[j];
    convolution(a0, b0);
    convolution(a1, b1);
    n = a0.size();
    a.resize(n);
    auto inv = Mint1(Mint0::p()).inv();
    for (int i = 0; i < n; ++i) {
        a[i] = a0[i].v + (lint) Mint0::p() * ((a1[i] - a0[i].v) * inv).v;
    }
}

// BEGIN CUT HERE
struct Bint {
    bool neg;
    string s;
    Bint() : neg(false), s("0") {}
    Bint(const string& x) : neg(x[0] == '-'), s(x.substr(neg)) {}
    Bint(lint x) : neg(x < 0), s(to_string(abs(x))) {}
    Bint(bool neg, const string& s) : neg(neg), s(s) {}
    Bint operator+() const { return *this; }
    Bint operator-() const { return {!neg, s}; }
    explicit operator bool() const noexcept { return s != "0"; }
    bool operator!() const noexcept { return !(bool) *this; }
    Bint operator*(const Bint& r) const { return Bint(*this) *= r; }
    Bint operator/(const Bint& r) const { return Bint(*this) /= r; }
    Bint operator%(const Bint& r) const { return Bint(*this) %= r; }
    Bint operator+(const Bint& r) const { return Bint(*this) += r; }
    Bint operator-(const Bint& r) const { return Bint(*this) -= r; }
    bool operator<(const Bint& r) const {
        if (neg != r.neg) return neg;
        return neg ^ (s.size() != r.s.size() ? s.size() < r.s.size() : s < r.s);
    }
    bool operator>(const Bint& r) const { return r < *this; }
    bool operator<=(const Bint& r) const { return !(*this > r); }
    bool operator>=(const Bint& r) const { return !(*this < r); }
    bool operator==(const Bint& r) const { return neg == r.neg and s == r.s; }
    bool operator!=(const Bint& r) const { return !(*this == r); }
    Bint& operator*=(const Bint& r) {
        if (!*this or !r) {
        neg = false, s = "0";
        return *this;
        }
        neg ^= r.neg;
        auto t = r.s;
        if (s.size() + t.size() < 20) {
        s = to_string(stoull(s) * stoull(t));
        return *this;
        }
        constexpr int D = 6;
        constexpr int B = 1e6;
        V<lint> a;
        for (int i = s.size(); i > 0; i -= D) {
        a.push_back(stoi(s.substr(max(i - D, 0), min(D, i))));
        }
        V<lint> b;
        for (int i = t.size(); i > 0; i -= D) {
        b.push_back(stoi(t.substr(max(i - D, 0), min(D, i))));
        }
        convolution(a, b);
        V<> res;
        lint c = 0;
        for (int i = 0; i < (int) a.size(); ++i) {
        res.push_back((c += a[i]) % B);
        c /= B;
        }
        s = to_string(c);
        while (!res.empty()) {
        auto t = to_string(res.back());
        while (t.size() < D) t = '0' + t;
        s += t;
        res.pop_back();
        }
        int i = 0;
        while (i < (int) s.size() and s[i] == '0') ++i;
        s = s.substr(i);
        return *this;
    }
    Bint& operator/=(const Bint& r) {
        assert(r);
        auto t = r.s;
        if (Bint(s) < Bint(t)) {
        neg = false, s = "0";
        return *this;
        }
        neg ^= r.neg;
        string res;
        for (int i = s.size() - t.size(); i >= 0; --i) {
        char c = '0';
        while (Bint(s) >= Bint(t + string(i, '0'))) {
            s = (Bint(s) - Bint(t + string(i, '0'))).s;
            ++c;
        }
        res += c;
        }
        s = res;
        int i = 0;
        while (i < (int) s.size() and s[i] == '0') ++i;
        s = s.substr(i);
        return *this;
    }
    Bint& operator%=(const Bint& r) { return *this -= *this / r * r; }
    Bint& operator+=(const Bint& r) {
        auto t = r.s;
        reverse(begin(s), end(s));
        reverse(begin(t), end(t));
        while (s.size() < t.size()) s += '0';
        while (t.size() < s.size()) t += '0';
        s += '0', t += '0';
        if (neg == r.neg) {
        int c = 0;
        for (int i = 0; i < (int) s.size(); ++i) {
            if ((s[i] += t[i] - '0' + c) > '9') {
            s[i] -= 10;
            c = 1;
            } else c = 0;
        }
        } else {
        if (neg) swap(s, t);
        s.back() = '1';
        int c = 0;
        for (int i = 0; i < (int) s.size(); ++i) {
            if ((s[i] -= t[i] - '0' + c) < '0') {
            s[i] += 10;
            c = 1;
            } else c = 0;
        }
        if (neg = s.back() == '0') {
            int i = 0;
            while (s[i] == '0') ++i;
            s[i] = '0' + 10 - (s[i] - '0');
            while (++i < (int) s.size() - 1) s[i] = '9' - (s[i] - '0');
        } else s.back() = '0';
        }
        while (s.size() > 1 and s.back() == '0') s.pop_back();
        reverse(begin(s), end(s));
        return *this;
    }
    Bint& operator-=(const Bint& r) { return *this += -r; }
    template<class Z> friend Bint operator*(Z l, const Bint& r) { return Bint(l) *= r; }
    template<class Z> friend Bint operator/(Z l, const Bint& r) { return Bint(l) /= r; }
    template<class Z> friend Bint operator%(Z l, const Bint& r) { return Bint(l) %= r; }
    template<class Z> friend Bint operator+(Z l, const Bint& r) { return Bint(l) += r; }
    template<class Z> friend Bint operator-(Z l, const Bint& r) { return Bint(l) -= r; }
    friend ostream& operator<<(ostream& os, const Bint& r) { if (r.neg) os << '-'; return os << r.s; }
    friend istream& operator>>(istream& is, Bint& r) { string x; is >> x; r = x; return is; }
    template<class Z> friend bool operator==(Z l, const Bint& r) { return Bint(l) == r; }
    template<class Z> friend bool operator!=(Z l, const Bint& r) { return !(l == r); }
};


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

    Bint T, A, B; cin >> T >> A >> B;
    Bint l = A * B / __gcd(A, B);
    Bint ans = 1 + (T - 1) / A + (T - 1) / B - (T - 1) / l;
    cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード