結果
問題 | No.2902 ZERO!! |
ユーザー |
|
提出日時 | 2024-09-27 21:57:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 415 ms / 2,000 ms |
コード長 | 3,259 bytes |
コンパイル時間 | 1,278 ms |
コンパイル使用メモリ | 116,700 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-27 21:57:30 |
合計ジャッジ時間 | 7,806 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <map>#include <set>#include <queue>using namespace std;typedef long long ll;const int INF = 1<<30;const ll INFLL = 1LL<<60;const ll MOD = 998244353;const double INFD = 100000000.0;template<class T> T pow_mod(T A, T N, T M) {T res = 1 % M;A %= M;while (N) {if (N & 1) res = (res * A) % M;A = (A * A) % M;N >>= 1;}return res;}bool MillerRabin(long long N, vector<long long> A) {long long s = 0, d = N - 1;while (d % 2 == 0) {++s;d >>= 1;}for (auto a : A) {if (N <= a) return true;long long t, x = pow_mod<__int128_t>(a, d, N);if (x != 1) {for (t = 0; t < s; ++t) {if (x == N - 1) break;x = __int128_t(x) * x % N;}if (t == s) return false;}}return true;}bool is_prime(long long N) {if (N <= 1) return false;if (N == 2) return true;if (N % 2 == 0) return false;if (N < 4759123141LL)return MillerRabin(N, {2, 7, 61});elsereturn MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});}const int mod = 998244353;class mint {long long x;public:mint(long long x=0) : x((x%mod+mod)%mod) {}mint operator-() const {return mint(-x);}mint& operator+=(const mint& a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint& a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint& a) {(x *= a.x) %= mod;return *this;}mint operator+(const mint& a) const {mint res(*this);return res+=a;}mint operator-(const mint& a) const {mint res(*this);return res-=a;}mint operator*(const mint& a) const {mint res(*this);return res*=a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}// for prime modmint inv() const {return pow(mod-2);}mint& operator/=(const mint& a) {return (*this) *= a.inv();}mint operator/(const mint& a) const {mint res(*this);return res/=a;}friend ostream& operator<<(ostream& os, const mint& m){os << m.x;return os;}};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);ll n; cin >> n;//nを素因数分解するmap<ll, ll> m;for (int i = 2; i <= n; i++){if (!is_prime(i)) continue;ll cnt = 0;ll j = i;while(j <= n){cnt += n / j;j *= i;}m[cnt]++;}//for (auto [k, v] : m) cout << k << " " << v << endl;mint ans = 0;for (int i = 1; i <= 1000000; i++){auto it = m.lower_bound(i);mint tmp = 1;for (auto j = it; j != m.end(); j++){auto [k, v] = *j;mint p = (k / i + 1);tmp *= p.pow(v);}ans += tmp - 1;}cout << ans << endl;}