結果

問題 No.1760 Setwise Coprime
コンテスト
ユーザー dekomori_sanae
提出日時 2022-02-24 15:48:45
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 58 ms / 2,000 ms
コード長 5,293 bytes
コンパイル時間 987 ms
コンパイル使用メモリ 96,884 KB
実行使用メモリ 15,760 KB
最終ジャッジ日時 2024-07-02 12:54:26
合計ジャッジ時間 3,753 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 998244353;
const ll INF = 1e16;

struct Eratosthenes {

    vl isprime;  // isprime[i] : iが素数なら1
    vl minfactor;  // minfactor[i] : iを割り切る最小の素数
    vl mobius;  // mobius[i] : メビウス関数 μ(i)

    Eratosthenes(ll n) : isprime(n+1, 1), 
                         minfactor(n+1, -1), 
                         mobius(n+1, 1) {
        isprime[1] = 0;
        minfactor[1] = 1;
        exrep(p, 2, n) {
            if(!isprime[p]) {
                continue;
            }
            minfactor[p] = p;
            mobius[p] = -1;
            for(ll q = 2*p; q <= n; q += p) {
                isprime[q] = 0;
                if(minfactor[q] == -1) {
                    minfactor[q] = p;
                }
                if((q / p) % p == 0) {
                    mobius[q] = 0;
                }
                else {
                    mobius[q] = -mobius[q];
                }
            }
        }
    }

    // 高速素因数分解。O(log(n))でnを素因数分解する
    vector<P> factorize(ll n) {  // (素因数, 指数) のvectorを返す
        vector<P> res;
        while(n > 1) {
            ll p = minfactor[n];
            ll i = 0;
            while(minfactor[n] == p) {
                n /= p;
                i++;
            }
            res.emplace_back(make_pair(p, i));
        }   
        return res;
    }

    // 高速約数列挙。O(σ(n))でnの約数を求める。σ(n)はnの約数の個数
    vl divisors(ll n) {
        vl res({1});
        auto pf = factorize(n);
        for(auto p : pf) {
            ll s = res.size();
            rep(i, s) {
                ll x = 1;
                rep(j, p.second) {
                    x *= p.first;
                    res.pb(res[i] * x);
                }
            }
        }
        return res;
    }
};

// エラトステネスの篩。計算量はO(n*loglog(n))
vl Eratosthenes1(ll n) {
    vl isprime(n+1, 1);
    isprime[1] = 0;
    exrep(p, 2, n) {
        if(!isprime[p]) {
            continue;
        }
        for(ll q = 2*p; q <= n; q += p) {
            isprime[q] = 0;
        }
    }
    return isprime;
}

// 約数系高速ゼータ変換。計算量はO(n*loglog(n))
template<class T> void fast_zeta(vector<T> &f) {
    ll n = f.size();
    vl isprime = Eratosthenes1(n);
    exrep(p, 2, n-1) {
        if(!isprime[p]) {
            continue;
        }
        for(ll k = 1; k <= (n - 1) / p; k++) {
            f[k * p] += f[k];
            f[k * p] %= mod;
        }
    }
}   

// 約数系高速メビウス変換。計算量はO(n*loglog(n))
template<class T> void fast_mobius(vector<T> &F) {
    ll n = F.size();
    vl isprime = Eratosthenes1(n);
    exrep(p, 2, n-1) {
        if(!isprime[p]) {
            continue;
        }
        for(ll k = (n - 1) / p; k >= 1; k--) {
            F[k * p] += mod - F[k];
            F[k * p] %= mod; 
        }
    }
}

// LCM畳み込み。計算量はO(n*loglog(n))
template<class T> vector<T> lcm_convolution(const vector<T> &f, const vector<T> &g) {
    ll n = 200010;  // 配列の最大値を設定する
    vector<T> F(n), G(n), H(n);
    rep(i, f.size()) {
        F[i] = f[i];
    }
    rep(i, g.size()) {
        G[i] = g[i];
    }
    fast_zeta(F);
    fast_zeta(G);
    exrep(i, 1, n-1) {
        H[i] = F[i] * G[i] % mod;
    }
    fast_mobius(H);
    return H;
}

const ll MAX = 5;

ll inv[MAX];  // inv[i] : iの逆数のmod

void init() {
    inv[0] = inv[1] = 1;
    for(ll i = 1; i < MAX; i++) {
        if(i >= 2) {
            inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        }
    }
}

// a^n (mod.MOD)を求める。計算量はO(logn)
ll modpow(ll a, ll n, ll MOD = mod) {
    if(n == 0) {
        return 1;
    }
    if(n % 2 == 1) {
        return a * modpow(a, n-1, MOD) % MOD;
    }
    return modpow(a, n/2, MOD) * modpow(a, n/2, MOD) % MOD;
}

int main() {
    ll n;
    cin >> n;

    init();

    Eratosthenes e(n+1);

    ll m = 0;
    exrep(i, 1, n) {
        m += e.mobius[i];
        m %= mod;
    }

    vl a(n+1);
    exrep(i, 1, n) {
        a[i] = e.mobius[i] * modpow(2LL, n / i) % mod;
    }

    ll x = 0;
    exrep(i, 1, n) {
        x += a[i];
        x %= mod;
    }

    vl b = lcm_convolution(a, a);

    ll y = 0;
    exrep(i, 1, n) {
        y += b[i];
        y %= mod;
    }

    ll z = 0;
    exrep(i, 1, n) {
        z += b[i] * modpow(3 * inv[4] % mod, n / i);
        z %= mod;
    }

    ll ans = (m * m + x * x + z + 2*mod - y - 2 * m * x % mod) % mod;

    out(ans);
    re0;
}
0