#326570 (C++17) No.546 オンリー・ワン

提出ソース
結果

問題	No.546 オンリー・ワン
ユーザー	taotao54321
提出日時	2019-03-20 20:01:52
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	7 ms / 2,000 ms
コード長	10,967 bytes
コンパイル時間	2,136 ms
コンパイル使用メモリ	213,708 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-09-19 00:48:10
合計ジャッジ時間	3,105 ms
ジャッジサーバーID （参考情報）	judge3 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	3 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	7 ms 5,376 KB
testcase_10	AC	5 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
/**
 * 
 */

// {{{ header
#include <bits/stdc++.h>
using namespace std;

using i8   = int8_t;
using u8   = uint8_t;
using i16  = int16_t;
using u16  = uint16_t;
using i32  = int32_t;
using u32  = uint32_t;
using i64  = int64_t;
using u64  = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

using f32  = float;
using f64  = double;
using f80  = __float80;
using f128 = __float128;
// }}}

constexpr i64 INF = 1'010'000'000'000'000'000LL;

constexpr i64 MOD = 1'000'000'007LL;

constexpr f64 EPS = 1e-12;

constexpr f64 PI = 3.14159265358979323846;

// {{{ util
#define FOR(i, start, end) for(i64 i = (start), i##_end=(end); i < i##_end; ++i)
#define REP(i, n) FOR(i, 0, n)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(begin(cccc), end(cccc), ## __VA_ARGS__); })(c))
#define SLICE(f,c,l,r,...) (([&](decltype((c)) cccc, decltype((l)) llll, decltype((r)) rrrr) {\
    auto iiii = llll <= rrrr ? begin(cccc)+llll : end(cccc);\
    auto jjjj = llll <= rrrr ? begin(cccc)+rrrr : end(cccc);\
    return (f)(iiii, jjjj, ## __VA_ARGS__);\
})(c,l,r))

#define GENERIC(f) ([](auto&&... args) -> decltype(auto) { return (f)(forward<decltype(args)>(args)...); })

template<typename F>
class FixPoint {
public:
    explicit constexpr FixPoint(F&& f) : f_(forward<F>(f)) {}

    template<typename... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return f_(*this, forward<Args>(args)...);
    }

private:
    const F f_;
};

template<typename F>
decltype(auto) FIX(F&& f) {
    return FixPoint<F>(forward<F>(f));
}

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }

bool is_odd (i64 x) { return x % 2 != 0; }
bool is_even(i64 x) { return x % 2 == 0; }

template<typename T> i64 cmp(T x, T y) { return (y<x) - (x<y); }
template<typename T> i64 sgn(T x) { return cmp(x, T(0)); }

// Haskell の divMod と同じ
pair<i64,i64> divmod(i64 a, i64 b) {
    i64 q = a / b;
    i64 r = a % b;
    if((b>0 && r<0) || (b<0 && r>0)) {
        --q;
        r += b;
    }
    return {q,r};
}

i64 div_ceil(i64 a, i64 b) {
    i64 q = a / b;
    i64 r = a % b;
    if((b>0 && r>0) || (b<0 && r<0))
        ++q;
    return q;
}

i64 div_floor(i64 a, i64 b) {
    return divmod(a,b).first;
}

i64 modulo(i64 a, i64 b) {
    return divmod(a,b).second;
}

bool feq(f64 x, f64 y, f64 eps=EPS) {
    return fabs(x-y) < eps;
}

template<typename T, typename U>
bool chmax(T& xmax, const U& x) {
    if(xmax < x) {
        xmax = x;
        return true;
    }
    return false;
}

template<typename T, typename U>
bool chmin(T& xmin, const U& x) {
    if(x < xmin) {
        xmin = x;
        return true;
    }
    return false;
}

template<typename InputIt>
auto SUM(InputIt first, InputIt last) {
    using T = typename iterator_traits<InputIt>::value_type;
    return accumulate(first, last, T());
}

template<typename ForwardIt, typename UnaryOperation>
ForwardIt transform_self(ForwardIt first, ForwardIt last, UnaryOperation op) {
    return transform(first, last, first, op);
}

template<typename C>
void UNIQ(C& c) {
    c.erase(ALL(unique,c), end(c));
}

template<typename BinaryFunc, typename UnaryFunc>
auto ON(BinaryFunc bf, UnaryFunc uf) {
    return [bf,uf](const auto& x, const auto& y) {
        return bf(uf(x), uf(y));
    };
}

template<typename F>
auto LT_ON(F f) { return ON(less<>(), f); }

template<typename F>
auto GT_ON(F f) { return ON(greater<>(), f); }

char digit_chr(i64 n) {
    return static_cast<char>('0' + n);
}

i64 digit_ord(char c) {
    return c - '0';
}

char lower_chr(i64 n) {
    return static_cast<char>('a' + n);
}

i64 lower_ord(char c) {
    return c - 'a';
}

char upper_chr(i64 n) {
    return static_cast<char>('A' + n);
}

i64 upper_ord(char c) {
    return c - 'A';
}

template<typename T>
void FROM_STRING(const string& s, T& x) {
    istringstream in(s);
    in >> x;
}

template<typename T>
string TO_STRING(const T& x) {
    ostringstream out;
    out << x;
    return out.str();
}

template<typename InputIt>
string JOIN(InputIt first, InputIt last, const string& sep) {
    ostringstream out;
    while(first != last) {
        out << *first++;
        if(first != last)
            out << sep;
    }
    return out.str();
}

template<typename T>
void RD(T& x) {
    cin >> x;
#ifdef PROCON_LOCAL
    assert(cin);
#endif
}

template<typename T>
void RD(vector<T>& v, i64 n) {
    v.reserve(n);
    REP(_, n) {
        T e; RD(e);
        v.emplace_back(e);
    }
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
    for(auto first = begin(v), it = first; it != end(v); ++it) {
        if(it != first)
            out << ' ';
        out << *it;
    }
    return out;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1,T2>& p) {
    return out << '(' << p.first << ',' << p.second << ')';
}

void PRINT() {}

template<typename T, typename... TS>
void PRINT(const T& x, const TS& ...args) {
    cout << x;
    if(sizeof...(args)) {
        cout << ' ';
        PRINT(args...);
    }
}

template<typename... TS>
void PRINTLN(const TS& ...args) {
    PRINT(args...);
    cout << '\n';
}

template<typename T>
void DBG_IMPL(i64 line, const char* expr, const T& value) {
#ifdef PROCON_LOCAL
    cerr << "[L " << line << "]: ";
    cerr << expr << " = " << value << "\n";
#endif
}

#define DBG(expr) DBG_IMPL(__LINE__, #expr, (expr))
// }}}

// {{{ init
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
#ifdef PROCON_LOCAL
        cerr << fixed << setprecision(IOS_PREC);
#endif
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;
// }}}

// {{{ num

// 事前条件: a >= 0, b >= 0
i64 gcd_impl(i64 a, i64 b) {
    if(b == 0) return a;
    return gcd_impl(b, a%b);
}

// gcd(0,0) = 0
i64 gcd(i64 a, i64 b) {
    return gcd_impl(abs(a), abs(b));
}

// lcm(0,x) は未定義
i64 lcm(i64 a, i64 b) {
    assert(a != 0 && b != 0);
    a = abs(a);
    b = abs(b);
    return a / gcd_impl(a,b) * b;
}

// 事前条件: a >= 0, b >= 0
i64 extgcd_impl(i64 a, i64 b, i64& x, i64& y) {
    if(b == 0) {
        x = 1; y = 0;
        return a;
    }
    i64 g = extgcd_impl(b, a%b, y, x);
    y -= a/b * x;
    return g;
}

// g=gcd(a,b), および ax+by=g の整数解 (x0,y0) を求める
// (g,x0,y0) を返す
// g!=0 のとき、一般解は (x,y) = (x0+m*b/g, y0-m*a/g) で与えられる(mは整数)
tuple<i64,i64,i64> extgcd(i64 a, i64 b) {
    i64 x, y;
    i64 g = extgcd_impl(abs(a), abs(b), x, y);
    x *= sgn(a);
    y *= sgn(b);
    return make_tuple(g, x, y);
}

// 素因数分解
// (素因数,指数) のリストを返す
vector<pair<i64,i64>> factorize(i64 n) {
    assert(n >= 2);

    vector<pair<i64,i64>> res;

    i64 m = n;
    for(i64 i = 2; i*i <= n; ++i) {
        if(m == 1) break;
        i64 e = 0;
        while(m % i == 0) {
            ++e;
            m /= i;
        }
        if(e) res.emplace_back(i, e);
    }
    if(m > 1) res.emplace_back(m, 1);

    return res;
}

// 二分累乗
template<typename Monoid>
Monoid pow_binary(Monoid x, i64 e) {
    assert(e >= 0);

    Monoid res(1);  // 行列などの場合はここを適当に変える
    Monoid cur = x;
    while(e > 0) {
        if(e & 1)
            res *= cur;
        cur *= cur;
        e >>= 1;
    }
    return res;
}

// mod m での a の逆元
// a ⊥ m でなければならない
i64 inv_mod(i64 a, i64 m) {
    i64 g,x0; tie(g,x0,ignore) = extgcd(a, m);
    assert(g == 1);
    return modulo(x0, m);
}

template<i64 P>
struct ModPT {
    static_assert(P >= 2, "P must be a prime");
    i64 v_;  // [0,P)

    ModPT() : v_(0) {}
    ModPT(i64 v) : v_(modulo(v,P)) {}

    const ModPT operator-() const {
        return ModPT(-v_);
    }
    ModPT& operator+=(ModPT rhs) {
        v_ += rhs.v_;
        v_ %= P;
        return *this;
    }
    ModPT& operator-=(ModPT rhs) {
        v_ += P;
        v_ -= rhs.v_;
        v_ %= P;
        return *this;
    }
    ModPT& operator*=(ModPT rhs) {
        v_ *= rhs.v_;
        v_ %= P;
        return *this;
    }

    ModPT inv() const {
        return ModPT(inv_mod(v_,P));
    }
};

template<i64 P>
const ModPT<P> operator+(ModPT<P> lhs, ModPT<P> rhs) { return ModPT<P>(lhs) += rhs; }
template<i64 P>
const ModPT<P> operator+(ModPT<P> lhs, i64 rhs) { return ModPT<P>(lhs) += rhs; }
template<i64 P>
const ModPT<P> operator+(i64 lhs, ModPT<P> rhs) { return ModPT<P>(rhs) += lhs; }
template<i64 P>
const ModPT<P> operator-(ModPT<P> lhs, ModPT<P> rhs) { return ModPT<P>(lhs) -= rhs; }
template<i64 P>
const ModPT<P> operator-(ModPT<P> lhs, i64 rhs) { return ModPT<P>(lhs) -= rhs; }
template<i64 P>
const ModPT<P> operator-(i64 lhs, ModPT<P> rhs) { return ModPT<P>(rhs) -= lhs; }
template<i64 P>
const ModPT<P> operator*(ModPT<P> lhs, ModPT<P> rhs) { return ModPT<P>(lhs) *= rhs; }
template<i64 P>
const ModPT<P> operator*(ModPT<P> lhs, i64 rhs) { return ModPT<P>(lhs) *= rhs; }
template<i64 P>
const ModPT<P> operator*(i64 lhs, ModPT<P> rhs) { return ModPT<P>(rhs) *= lhs; }

template<i64 P>
ostream& operator<<(ostream& out, ModPT<P> x) {
    return out << x.v_;
}

using ModP = ModPT<MOD>;

// F(0) = 0
// F(1) = 1
// F(n) = F(n-1) + F(n-2)
//
// // decltype(auto) で受けると SIZE() が使える (auto だとポインタになってしまう)
// decltype(auto) fib = fibonacci<1000>();
template<size_t N>
ModP (&fibonacci())[N] {
    static_assert(N >= 2, "");
    static ModP fib[N];

    fib[0] = 0;
    fib[1] = 1;
    FOR(i, 2, N) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib;
}

// }}}

//--------------------------------------------------------------------

i64 BIT(i64 x, i64 i) {
    return (x>>i) & 1;
}

// [1,n] のうち ds 内のどれかで割り切れるものの数
i64 f(i64 n, const vector<i64>& ds) {
    i64 res = 0;
    i64 m = SIZE(ds);
    FOR(i, 1, (1LL<<m)) {
        i64 d = 1;
        REP(j, m) {
            if(BIT(i,j))
                d = lcm(d, ds[j]);
        }
        i64 sign = is_odd(__builtin_popcountll(i)) ? 1 : -1;
        res += sign * n/d;
    }
    return res;
}

// [l,h] のうち ds 内のどれかで割り切れるものの数
i64 g(i64 l, i64 h, const vector<i64>& ds) {
    if(l == 1) return f(h,ds);
    return f(h,ds) - f(l-1,ds);
}

void solve() {
    i64 N; RD(N);
    i64 L,H; RD(L); RD(H);
    vector<i64> A; RD(A, N);

    i64 x_all = g(L, H, A);

    i64 ans = 0;
    REP(i, N) {
        vector<i64> ds(A);
        ds.erase(begin(ds)+i);
        ans += x_all - g(L, H, ds);
    }

    // * MOD はとった?
    // * 違うやつ提出してない?
    // * 違うやつテストしてない?
    PRINTLN(ans);
}

signed main() {
    

    solve();

    return 0;
}
yukicoder

結果

テストケース

ソースコード
