結果
問題 |
No.2902 ZERO!!
|
ユーザー |
![]() |
提出日時 | 2025-10-02 11:31:30 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 2,544 bytes |
コンパイル時間 | 7,082 ms |
コンパイル使用メモリ | 335,496 KB |
実行使用メモリ | 16,808 KB |
最終ジャッジ日時 | 2025-10-02 11:31:51 |
合計ジャッジ時間 | 11,908 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vmi = vector<mint>; using vvmi = vector<vmi>; using vvvmi = vector<vvmi>; #define all(a) (a).begin(), (a).end() #define rep2(i, m, n) for (int i = (m); i < (n); ++i) #define rep(i, n) rep2(i, 0, n) #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) class Primes{ private: int size_p; vector<bool> is_p; vector<int> primes; vector<int> minfactor; vector<int> mobius; void eratos(int n){ for(int i=2; i<=n; i++){ if(minfactor[i] < i)continue; primes.emplace_back(i); mobius[i] = -1; is_p[i] =true; for(int j = 2*i; j<=n; j+=i){ minfactor[j] = min(i, minfactor[j]); mobius[j] = ((j/i) % i == 0) ? 0 : -mobius[j]; } } } public: Primes(int n){ size_p = n; rep(i, size_p+1)is_p.emplace_back(false); rep(i, size_p+1)minfactor.emplace_back(i); rep(i, size_p+1)mobius.push_back(1); mobius[1] = 1; eratos(size_p); } bool isprime(int n){ return is_p[n]; } vector<int> listPrimes(){ return primes; } int getMobius(int n){return mobius[n];} }; int main(){ int n; cin >> n; Primes pr(n); vi lp = pr.listPrimes(); int len = lp.size(); vll cnt(len, 0); rep(i, len){ ll p = (ll)lp[i]; for(ll j = p; j <= n; j*=p)cnt[i] += n/j; } int mx = cnt[0]; vmi cntmin(mx + 1, mint(0)); queue<ll> q; rep(i, len)q.push(cnt[i]); rep2(i, 1, mx + 1){ mint tmp = mint(1); vll del; int l = q.size(); rep(j, l){ ll u = q.front(); q.pop(); tmp *= mint(u/i) + mint(1); if(u >= i)q.push(u); } cntmin[i] = tmp - mint(1); } mint ans = mint(0); rep2(i, 1, mx) ans += mint(i)*(cntmin[i] - cntmin[i+1]); ans += mint(mx)*cntmin[mx]; cout << ans.val() << endl; return 0; }