Submission #15385832


Source Code Expand

Copy
// May this submission get accepted
#include <bits/stdc++.h>

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using namespace std;

// AtCoder/Codeforces 用 デバッグ検知
#ifdef ONLINE_JUDGE
constexpr bool DEBUG_MODE = false;
#else
constexpr bool DEBUG_MODE = true;
#endif

// エイリアス (補完・コンパイルが重くなる)
// #include <boost/multiprecision/cpp_int.hpp>
// using mll = boost::multiprecision::cpp_int;

// 汎用マクロ
#define ALLOF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define STEP(i, is, ie, step) for (long long i=(is), i##_end=(ie), i##_step = (step); i<=i##_end; i+=i##_step)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define FOREACH(i,q) for (auto &i : q)
template<typename T, typename U> bool chmax(T &a, const U b) { if (a < b) {a = b; return true;} return false; }
template<typename T, typename U> bool chmin(T &a, const U b) { if (a > b) {a = b; return true;} return false; }
constexpr int INF = numeric_limits<int>::max();
constexpr long long LINF = numeric_limits<long long>::max();
constexpr long double EPS = 1e-10L;
#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")
#define IIF(q,t,f) ((q) ? (t) : (f))
#define DUMP(q) DUMP_FUNC(q, #q, __FILE__, __LINE__)
template <typename T> void DUMP_PROC(T x) { if (is_integral<T>() || is_floating_point<T>()) cerr << "\e[32m" << x << "\e[m"; else cerr << x; }
template<> void DUMP_PROC<char>(char x) { cerr << "\e[36m\'" << x << "\'\e[m"; }
template<> void DUMP_PROC<string>(string x) { cerr << "\e[33m\"" << x << "\"\e[m"; }
template <typename T, typename U> void DUMP_PROC(pair<T, U> x) { cerr << "{"; DUMP_PROC(x.first); cerr << ", "; DUMP_PROC(x.second); cerr << "}"; }
template <typename ...T, typename U, U... Seq> void DUMP_PROC(tuple<T...> &x, integer_sequence<U, Seq...>) { (void)(int[]){(cerr << ((const char*[]){"", ", "})[!!Seq] << (DUMP_PROC(get<Seq>(x)), ""), 0)...}; }
template <typename ...T> void DUMP_PROC(tuple<T...> x) {cerr << "{"; DUMP_PROC(x, index_sequence_for<T...>()); cerr << "}";}
template <typename T> void DUMP_PROC(vector<T> x) { cerr << "["; for (auto &xi : x) { DUMP_PROC(xi); cerr << (&xi != &*x.rbegin()?", ":""); } cerr << "]"; }
template <typename T> void DUMP_FUNC(T x, const char* name, const char* fn, int ln) { cerr << "\e[32m[DEBUG]\e[m " << name << ": "; DUMP_PROC(x); cerr << " @ " << fn << "(" << ln << ")" << endl; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// 標準入出力
struct qin { // query input
    size_t sz;
    qin(size_t _sz = 1) : sz(_sz) {}
    template <typename T> operator T () const { T a; cin >> a; return a; }
    template <typename T> operator vector<T> () const { vector<T> a(sz); for (size_t i = 0; i < sz; i++) cin >> a[i]; return a; }
    template <typename T, typename U> operator pair<T, U> () const { T f; U s; cin >> f >> s; return pair<T, U>(f, s); }
};
qin in1; // input one
template <typename T> void say(const T x, const char* end = "\n") { cout << x << end; }
void say(const ld x, const char* end = "\n") { cout << setprecision(30) << x << end; }
template <typename T> void say(const vector<T> x, const char* sep = " ", const char* end = "\n") { REP(i, x.size()) { cout << x[i] << (i+1 == i_len ? end : sep); } }
template <typename T> void say(const vector<vector<T>> x, const char* sep = " ", const char* end = "\n") { REP(i, x.size()) { say(x[i], sep, end); } }

// モジュール
// [[LIBRARY]] zeta_divisor.cpp
// [Inclusion] zeta_divisor.cpp
// 高速約数ゼータ変換 O(VlogV); V being x.size()
// fzt(x)[s] == Σ_{s|t/t|s} x[t] (ただし∀i,0|iとする)
// inv: これをtrueにするとメビウス, subset: これをtrueにするとt|s
template<typename T>
vector<T> fdzt(const vector<T> &x, const bool inv = false, const bool subset = false) {
    const size_t n = x.size();
    vector<uint_fast8_t> sieve(x.size(), true);
    vector<T> a = x;
    if (inv) {
        for (size_t i = 1; i < n; i++) {
            a[i] -= a[0];
        }
    }
    for (size_t i = 2; i < n; i++) {
        if (!sieve[i]) continue;
        if (!subset) {
            if (inv) {
                for (size_t j = 1; i*j < n; j++) {
                    sieve[i*j] = false;
                    a[j] -= a[i*j];
                }
            } else {
                for (size_t j = (n-1)/i; j > 0; j--) {
                    sieve[i*j] = false;
                    a[j] += a[i*j];
                }
            }
        } else {
            if (inv) {
                for (size_t j = (n-1)/i; j > 0; j--) {
                    sieve[i*j] = false;
                    a[i*j] -= a[j];
                }
            } else {
                for (size_t j = 1; i*j < n; j++) {
                    sieve[i*j] = false;
                    a[i*j] += a[j];
                }
            }
        }
    }
    if (!inv) {
        for (size_t i = 1; i < n; i++) {
            a[i] += a[0];
        }
    }
    return a;
}
// GCD/LCM畳み込み (x*y)[d] = Σ_{gcd/lcm(i,j)=d} x[i]*y[j], 但しgcd(x,0)==lcm(0,x)==x
template <typename T>
vector<T> convolve_zeta(const vector<T> &x, const vector<T> &y, const bool subset) {
    size_t n = max(x.size(), y.size());
    auto xc = x; xc.resize(n, 0);
    auto yc = y; yc.resize(n, 0);
    auto X = fdzt(xc, false, subset);
    auto Y = fdzt(yc, false, subset);
    for (size_t i = n; i--;) {
        X[i] *= Y[i];
    }
    return fdzt(X, true, subset);
}
template <typename T> vector<T> convolve_gcd(const vector<T> &x, const vector<T> &y) { return convolve_zeta(x, y, false); }
template <typename T> vector<T> convolve_lcm(const vector<T> &x, const vector<T> &y) { return convolve_zeta(x, y, true ); }

// [[/LIBRARY]]

// 処理内容
int main() {
    
    ios::sync_with_stdio(false); // stdioを使うときはコメントアウトすること
    cin.tie(nullptr);            // インタラクティブ問題ではコメントアウトすること
    
    ll n, m; cin >> n >> m;
    vector<ll> a = qin(n);
    ll maxa = max(m, *max_element(ALLOF(a)));

    vector<ll> b(maxa+1, 0LL);
    FOREACH(x, a) b[x]++;
    auto B = fdzt(b);

    vector<vector<ll>> dt(m+1);
    vector<ll> sieve(m+1, 0);
    
    RANGE(i, 1, m) {

        // Divisors
        if (i == 1) {
            dt[i].push_back(1);
        } else {
            if (!sieve[i]) {
                STEP(j, i, m, i) {
                    if (!sieve[j]) sieve[j] = i;
                }
            }
            ll j = i / sieve[i];
            FOREACH(x, dt[j]) {
                dt[i].push_back(x);
                dt[i].push_back(x * sieve[i]);
            }
            UNIQUE(dt[i]);
        }

        // Factors
        vector<ll> f;
        for (ll j = i; j > 1; ) {
            if (f.empty() || f.back() != sieve[j]) {
                f.push_back(sieve[j]);
            }
            j /= sieve[j];
        }
        
        // Zeta
        set<ll> ds(ALLOF(dt[i]));
        map<ll, ll> c;
        FOREACH(i, dt[i]) c[i] = B[i];
        FOREACH(p, f) {
            FOREACH(i, dt[i]) {
                if (ds.find(i*p) != ds.end()) {
                    c[i] -= c[i*p];
                }
            }
        }
        say(c[1]);

    }
    
}

Submission Info

Submission Time
Task A - Uncommon
User ganmodokix
Language C++ (GCC 9.2.1)
Score 600
Code Size 7852 Byte
Status AC
Exec Time 335 ms
Memory 23820 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 46
Set Name Test Cases
Sample a01, a02, a03
All a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46
Case Name Status Exec Time Memory
a01 AC 6 ms 3476 KB
a02 AC 5 ms 4932 KB
a03 AC 2 ms 3656 KB
b04 AC 2 ms 3576 KB
b05 AC 323 ms 22920 KB
b06 AC 16 ms 5700 KB
b07 AC 334 ms 23752 KB
b08 AC 328 ms 23820 KB
b09 AC 324 ms 23076 KB
b10 AC 325 ms 23016 KB
b11 AC 327 ms 23168 KB
b12 AC 327 ms 23360 KB
b13 AC 329 ms 23316 KB
b14 AC 330 ms 23476 KB
b15 AC 328 ms 23512 KB
b16 AC 328 ms 23524 KB
b17 AC 335 ms 23756 KB
b18 AC 332 ms 23660 KB
b19 AC 328 ms 23752 KB
b20 AC 334 ms 23668 KB
b21 AC 333 ms 23596 KB
b22 AC 331 ms 23664 KB
b23 AC 327 ms 23316 KB
b24 AC 331 ms 23428 KB
b25 AC 325 ms 23172 KB
b26 AC 329 ms 23472 KB
b27 AC 332 ms 23680 KB
b28 AC 329 ms 23032 KB
b29 AC 329 ms 23144 KB
b30 AC 328 ms 22988 KB
b31 AC 332 ms 23204 KB
b32 AC 329 ms 23336 KB
b33 AC 328 ms 23332 KB
b34 AC 332 ms 23440 KB
b35 AC 324 ms 23376 KB
b36 AC 333 ms 23472 KB
b37 AC 332 ms 23532 KB
b38 AC 324 ms 23620 KB
b39 AC 317 ms 23088 KB
b40 AC 328 ms 23300 KB
b41 AC 325 ms 23336 KB
b42 AC 331 ms 23528 KB
b43 AC 330 ms 23764 KB
b44 AC 15 ms 5492 KB
b45 AC 15 ms 5076 KB
b46 AC 33 ms 6112 KB