cp-library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub Joe75792433/cp-library

:heavy_check_mark: test/aoj/ALDS1_1_C/ALDS1_1_C-test-00.cpp

Depends on

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_C
#include <bits/stdc++.h>
#include <atcoder/modint>
#include "cplib/is_prime.hpp"
#include "cplib/vector_io.hpp"

using namespace std;
using namespace atcoder;
using namespace cplib;

#ifdef DEBUG
template <typename T, typename U> void debug_print(T var_name, U value) {
    cerr << var_name << ": " << value << endl;
}
#define debug(x) debug_print(#x, x)
constexpr bool is_debug = true;
#else
//#pragma GCC target("arch=skylake-avx512")
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define debug(x)
constexpr bool is_debug = false;
#endif

using ll = long long;
template <typename T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using vector2 = vector<vector<T>>;
template <typename T> using vector3 = vector<vector2<T>>;
template <typename T> using vector4 = vector<vector3<T>>;
template <typename T> using vector5 = vector<vector4<T>>;
template <typename T> using vector6 = vector<vector5<T>>;
template <typename T>
inline vector2<T> make_vector2(const size_t l0,
                               const size_t l1,
                               const T& init = T()) {
    return vector2<T>(l0, vector<T>(l1, init));
}
template <typename T>
inline vector3<T> make_vector3(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const T& init = T()) {
    return vector3<T>(l0, make_vector2<T>(l1, l2, init));
}
template <typename T>
inline vector4<T> make_vector4(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const size_t l3,
                               const T& init = T()) {
    return vector4<T>(l0, make_vector3<T>(l1, l2, l3, init));
}
template <typename T>
inline vector5<T> make_vector5(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const size_t l3,
                               const size_t l4,
                               const T& init = T()) {
    return vector5<T>(l0, make_vector4<T>(l1, l2, l3, l4, init));
}
template <typename T>
inline vector6<T> make_vector6(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const size_t l3,
                               const size_t l4,
                               const size_t l5,
                               const T& init = T()) {
    return vector6<T>(l0, make_vector5<T>(l1, l2, l3, l4, l5, init));
}

#define rep(...) overloadrep(__VA_ARGS__, rep4_, rep3_, rep2_)(__VA_ARGS__)
#define overloadrep(_1, _2, _3, _4, repn_, ...) repn_
#define rep2_(i, n) rep4_(i, 0, n, 1)
#define rep3_(i, a, b) rep4_(i, a, b, 1)
#define rep4_(i, a, b, s) for (auto i = (a); i < (b); i += (s))
#define repr(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define foreach(x, a) for (auto& x : (a))

inline void din_() {}
template <class Head, class... Tail>
inline void din_(Head&& head, Tail&&... tail) {
    cin >> head;
    din_(move(tail)...);
}
#define din(T, ...) \
    T __VA_ARGS__;  \
    din_(__VA_ARGS__)

inline void dout() { cout << '\n'; }
template <typename Head, typename... Tail>
inline void dout(const Head& head, const Tail&... tail) {
    cout << head;
    if constexpr (sizeof...(tail) > 0) {
        cout << ' ';
    }
    dout(tail...);
}

template <class T = ll> inline T IN() {
    T x;
    cin >> x;
    return (x);
}

inline void YesNo(bool b, const string yes, const string no) noexcept {
    cout << (b ? yes : no) << '\n';
}
inline void YES(bool b) noexcept { YesNo(b, "YES", "NO"); }
inline void Yes(bool b) noexcept { YesNo(b, "Yes", "No"); }
inline void POSSIBLE(bool b) noexcept { YesNo(b, "POSSIBLE", "IMPOSSIBLE"); }
inline void Possible(bool b) noexcept { YesNo(b, "Possible", "Impossible"); }
inline void FIRST(bool b) noexcept { YesNo(b, "FIRST", "SECOND"); }
inline void First(bool b) noexcept { YesNo(b, "First", "Second"); }

#define all(x) (x).begin(), (x).end()
template <typename T> inline int siz(const T& x) { return int(x.size()); }
template <typename IntLike> constexpr int Pcnt(const IntLike n) {
    return popcount(static_cast<unsigned long long>(n));
}
template <typename IntLike> constexpr ll Bit(const IntLike n) {
    return 1LL << n;
}
template <typename T> inline void uniq(vector<T>& v) {
    auto result = ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T1, class T2>
    requires totally_ordered_with<T1, T2> && assignable_from<T1&, T2>
constexpr bool chmax(T1& a, const T2& b) noexcept {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T1, class T2>
    requires totally_ordered_with<T1, T2> && assignable_from<T1&, T2>
constexpr bool chmin(T1& a, const T2& b) noexcept {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr char enl = '\n';
constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr long double eps = 1e-10;
constexpr int INF = 1'010'000'000;                 // 1e9
constexpr ll llINF = 3'010'000'000'000'000'000LL;  // 3e18
//constexpr ll MOD = 1'000'000'007LL;
constexpr ll MOD = 998244353LL;
using mint = static_modint<MOD>;

void Main([[maybe_unused]] int testcase_i) {
    din(int, n);
    int ans = 0;
    rep(i, n) if (is_prime(IN()))++ ans;
    dout(ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int t = 1;
    //cin >> t;
    rep(i, t) Main(i);
}
#line 1 "test/aoj/ALDS1_1_C/ALDS1_1_C-test-00.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_C
#include <bits/stdc++.h>
#include <atcoder/modint>
#line 2 "cplib/is_prime.hpp"

#line 2 "cplib/miller_rabin.hpp"

#include <bit>
#line 5 "cplib/miller_rabin.hpp"
#include <ranges>
#line 2 "cplib/pow_mod_ull.hpp"

#line 4 "cplib/pow_mod_ull.hpp"

namespace cplib {

// (x ^ n) mod m を繰り返し二乗法で求める
// x >= 0, n >= 0, m >= 1
uint64_t pow_mod_ull(uint64_t x, uint64_t n, const uint64_t m) {
    uint64_t result = ((n % 2 == 1) ? x : 1) % m;
    for (n /= 2; n > 0; n /= 2) {
        x = static_cast<uint64_t>(__uint128_t(x) * __uint128_t(x) %
                                  __uint128_t(m));
        if (n % 2 == 1) {
            result = static_cast<uint64_t>(__uint128_t(result) *
                                           __uint128_t(x) % __uint128_t(m));
        }
    }
    return result;
}

}  // namespace cplib
#line 8 "cplib/miller_rabin.hpp"

namespace cplib {

// n が素数であるかをミラーラビン法で判定する
// vector で渡した整数を証人とする
bool miller_rabin(const uint64_t n, const std::vector<uint64_t>& wits) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    const int s = std::countr_zero(n - 1);
    const uint64_t d = (n - 1) >> s;

    for (const uint64_t a :
         wits | std::views::transform([n](uint64_t x) { return x % n; })) {
        if (a == 0) continue;

        uint64_t tmp = pow_mod_ull(a, d, n);
        if (tmp == 1) continue;

        for (int i = 0; tmp != n - 1; ++i) {
            if (i == s - 1) return false;
            tmp = pow_mod_ull(tmp, 2, n);
        }
    }

    return true;
}

}  // namespace cplib
#line 6 "cplib/is_prime.hpp"

namespace cplib {

// n が素数であるかを判定する(Miller-Rabin法)
// n < 2^64, q <= 10^5 程度が間に合う
bool is_prime(const uint64_t n) {
    if (n < 4759123141ULL) {
        return miller_rabin(n, {2, 7, 61});
    } else {
        return miller_rabin(n,
                            {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
    }
}

}  // namespace cplib
#line 2 "cplib/vector_io.hpp"

#line 6 "cplib/vector_io.hpp"

namespace cplib {

template <typename T>
inline std::istream& operator>>(std::istream& is, std::vector<T>& v) {
#ifdef DEBUG
    assert(v.size() != 0);
#endif
    for (auto& x : v) is >> x;
    return is;
}

template <typename T>
inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    const size_t len = v.size();
    for (size_t i = 0; i < len - 1; ++i) os << v[i] << ' ';
    if (len > 0) os << v[len - 1];
    return os;
}

}  // namespace cplib
#line 6 "test/aoj/ALDS1_1_C/ALDS1_1_C-test-00.cpp"

using namespace std;
using namespace atcoder;
using namespace cplib;

#ifdef DEBUG
template <typename T, typename U> void debug_print(T var_name, U value) {
    cerr << var_name << ": " << value << endl;
}
#define debug(x) debug_print(#x, x)
constexpr bool is_debug = true;
#else
//#pragma GCC target("arch=skylake-avx512")
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define debug(x)
constexpr bool is_debug = false;
#endif

using ll = long long;
template <typename T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using vector2 = vector<vector<T>>;
template <typename T> using vector3 = vector<vector2<T>>;
template <typename T> using vector4 = vector<vector3<T>>;
template <typename T> using vector5 = vector<vector4<T>>;
template <typename T> using vector6 = vector<vector5<T>>;
template <typename T>
inline vector2<T> make_vector2(const size_t l0,
                               const size_t l1,
                               const T& init = T()) {
    return vector2<T>(l0, vector<T>(l1, init));
}
template <typename T>
inline vector3<T> make_vector3(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const T& init = T()) {
    return vector3<T>(l0, make_vector2<T>(l1, l2, init));
}
template <typename T>
inline vector4<T> make_vector4(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const size_t l3,
                               const T& init = T()) {
    return vector4<T>(l0, make_vector3<T>(l1, l2, l3, init));
}
template <typename T>
inline vector5<T> make_vector5(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const size_t l3,
                               const size_t l4,
                               const T& init = T()) {
    return vector5<T>(l0, make_vector4<T>(l1, l2, l3, l4, init));
}
template <typename T>
inline vector6<T> make_vector6(const size_t l0,
                               const size_t l1,
                               const size_t l2,
                               const size_t l3,
                               const size_t l4,
                               const size_t l5,
                               const T& init = T()) {
    return vector6<T>(l0, make_vector5<T>(l1, l2, l3, l4, l5, init));
}

#define rep(...) overloadrep(__VA_ARGS__, rep4_, rep3_, rep2_)(__VA_ARGS__)
#define overloadrep(_1, _2, _3, _4, repn_, ...) repn_
#define rep2_(i, n) rep4_(i, 0, n, 1)
#define rep3_(i, a, b) rep4_(i, a, b, 1)
#define rep4_(i, a, b, s) for (auto i = (a); i < (b); i += (s))
#define repr(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define foreach(x, a) for (auto& x : (a))

inline void din_() {}
template <class Head, class... Tail>
inline void din_(Head&& head, Tail&&... tail) {
    cin >> head;
    din_(move(tail)...);
}
#define din(T, ...) \
    T __VA_ARGS__;  \
    din_(__VA_ARGS__)

inline void dout() { cout << '\n'; }
template <typename Head, typename... Tail>
inline void dout(const Head& head, const Tail&... tail) {
    cout << head;
    if constexpr (sizeof...(tail) > 0) {
        cout << ' ';
    }
    dout(tail...);
}

template <class T = ll> inline T IN() {
    T x;
    cin >> x;
    return (x);
}

inline void YesNo(bool b, const string yes, const string no) noexcept {
    cout << (b ? yes : no) << '\n';
}
inline void YES(bool b) noexcept { YesNo(b, "YES", "NO"); }
inline void Yes(bool b) noexcept { YesNo(b, "Yes", "No"); }
inline void POSSIBLE(bool b) noexcept { YesNo(b, "POSSIBLE", "IMPOSSIBLE"); }
inline void Possible(bool b) noexcept { YesNo(b, "Possible", "Impossible"); }
inline void FIRST(bool b) noexcept { YesNo(b, "FIRST", "SECOND"); }
inline void First(bool b) noexcept { YesNo(b, "First", "Second"); }

#define all(x) (x).begin(), (x).end()
template <typename T> inline int siz(const T& x) { return int(x.size()); }
template <typename IntLike> constexpr int Pcnt(const IntLike n) {
    return popcount(static_cast<unsigned long long>(n));
}
template <typename IntLike> constexpr ll Bit(const IntLike n) {
    return 1LL << n;
}
template <typename T> inline void uniq(vector<T>& v) {
    auto result = ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T1, class T2>
    requires totally_ordered_with<T1, T2> && assignable_from<T1&, T2>
constexpr bool chmax(T1& a, const T2& b) noexcept {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T1, class T2>
    requires totally_ordered_with<T1, T2> && assignable_from<T1&, T2>
constexpr bool chmin(T1& a, const T2& b) noexcept {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr char enl = '\n';
constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr long double eps = 1e-10;
constexpr int INF = 1'010'000'000;                 // 1e9
constexpr ll llINF = 3'010'000'000'000'000'000LL;  // 3e18
//constexpr ll MOD = 1'000'000'007LL;
constexpr ll MOD = 998244353LL;
using mint = static_modint<MOD>;

void Main([[maybe_unused]] int testcase_i) {
    din(int, n);
    int ans = 0;
    rep(i, n) if (is_prime(IN()))++ ans;
    dout(ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int t = 1;
    //cin >> t;
    rep(i, t) Main(i);
}

Test cases

Env Name Status Elapsed Memory
g++ testcase_00 :heavy_check_mark: AC 8 ms 0 MB
g++ testcase_01 :heavy_check_mark: AC 9 ms 0 MB
g++ testcase_02 :heavy_check_mark: AC 9 ms 0 MB
g++ testcase_03 :heavy_check_mark: AC 14 ms 0 MB
Back to top page