結果
問題 | No.2891 Mint |
ユーザー | Fu_L |
提出日時 | 2024-09-26 12:05:26 |
言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 176 ms / 2,000 ms |
コード長 | 4,662 bytes |
コンパイル時間 | 6,585 ms |
コンパイル使用メモリ | 275,748 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-26 12:05:45 |
合計ジャッジ時間 | 17,399 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 148 ms
5,248 KB |
testcase_01 | AC | 150 ms
5,376 KB |
testcase_02 | AC | 160 ms
5,376 KB |
testcase_03 | AC | 148 ms
5,376 KB |
testcase_04 | AC | 152 ms
5,376 KB |
testcase_05 | AC | 147 ms
5,376 KB |
testcase_06 | AC | 164 ms
5,376 KB |
testcase_07 | AC | 148 ms
5,376 KB |
testcase_08 | AC | 151 ms
5,376 KB |
testcase_09 | AC | 160 ms
5,376 KB |
testcase_10 | AC | 147 ms
5,376 KB |
testcase_11 | AC | 146 ms
5,376 KB |
testcase_12 | AC | 147 ms
5,376 KB |
testcase_13 | AC | 148 ms
5,376 KB |
testcase_14 | AC | 160 ms
5,376 KB |
testcase_15 | AC | 152 ms
5,376 KB |
testcase_16 | AC | 159 ms
5,376 KB |
testcase_17 | AC | 159 ms
5,376 KB |
testcase_18 | AC | 155 ms
5,376 KB |
testcase_19 | AC | 159 ms
5,376 KB |
testcase_20 | AC | 160 ms
5,376 KB |
testcase_21 | AC | 157 ms
5,376 KB |
testcase_22 | AC | 166 ms
5,376 KB |
testcase_23 | AC | 176 ms
5,376 KB |
testcase_24 | AC | 160 ms
5,376 KB |
testcase_25 | AC | 169 ms
5,376 KB |
testcase_26 | AC | 161 ms
5,376 KB |
testcase_27 | AC | 160 ms
5,376 KB |
testcase_28 | AC | 166 ms
5,376 KB |
testcase_29 | AC | 155 ms
5,376 KB |
testcase_30 | AC | 161 ms
5,376 KB |
testcase_31 | AC | 153 ms
5,376 KB |
testcase_32 | AC | 162 ms
5,376 KB |
testcase_33 | AC | 155 ms
5,376 KB |
testcase_34 | AC | 161 ms
5,376 KB |
testcase_35 | AC | 156 ms
5,376 KB |
testcase_36 | AC | 162 ms
5,376 KB |
testcase_37 | AC | 148 ms
5,376 KB |
testcase_38 | AC | 148 ms
5,376 KB |
testcase_39 | AC | 146 ms
5,376 KB |
testcase_40 | AC | 160 ms
5,376 KB |
testcase_41 | AC | 150 ms
5,376 KB |
testcase_42 | AC | 151 ms
5,376 KB |
testcase_43 | AC | 149 ms
5,376 KB |
testcase_44 | AC | 149 ms
5,376 KB |
testcase_45 | AC | 148 ms
5,376 KB |
testcase_46 | AC | 148 ms
5,376 KB |
testcase_47 | AC | 160 ms
5,376 KB |
testcase_48 | AC | 151 ms
5,376 KB |
testcase_49 | AC | 147 ms
5,376 KB |
testcase_50 | AC | 153 ms
5,376 KB |
testcase_51 | AC | 153 ms
5,376 KB |
testcase_52 | AC | 149 ms
5,376 KB |
testcase_53 | AC | 151 ms
5,376 KB |
testcase_54 | AC | 160 ms
5,376 KB |
testcase_55 | AC | 149 ms
5,376 KB |
testcase_56 | AC | 149 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using P = pair<ll, ll>; #define rep(i, a, b) for(ll i = a; i < b; ++i) #define rrep(i, a, b) for(ll i = a; i >= b; --i) constexpr ll inf = 4e18; struct SetupIO { SetupIO() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(30); } } setup_io; template <uint32_t m> struct StaticModint { using mint = StaticModint; static constexpr uint32_t mod() { return m; } static constexpr mint raw(uint32_t v) { mint a; a._v = v; return a; } constexpr StaticModint() : _v(0) {} template <class T> constexpr StaticModint(const T& v) { static_assert(is_integral_v<T>); if constexpr(is_signed_v<T>) { int64_t x = int64_t(v % int64_t(m)); if(x < 0) x += m; _v = uint32_t(x); } else _v = uint32_t(v % m); } constexpr uint32_t val() const { return _v; } constexpr mint& operator++() { return *this += 1; } constexpr mint& operator--() { return *this -= 1; } constexpr mint operator++(int) { mint res = *this; ++*this; return res; } constexpr mint operator--(int) { mint res = *this; --*this; return res; } constexpr mint& operator+=(mint rhs) { if(_v >= m - rhs._v) _v -= m; _v += rhs._v; return *this; } constexpr mint& operator-=(mint rhs) { if(_v < rhs._v) _v += m; _v -= rhs._v; return *this; } constexpr mint& operator*=(mint rhs) { return *this = *this * rhs; } constexpr mint& operator/=(mint rhs) { return *this *= rhs.inv(); } constexpr mint operator+() const { return *this; } constexpr mint operator-() const { return mint{} - *this; } constexpr mint pow(long long n) const { assert(0 <= n); if(n == 0) return 1; mint x = *this, r = 1; while(1) { if(n & 1) r *= x; n >>= 1; if(n == 0) return r; x *= x; } } constexpr mint inv() const { if constexpr(prime) { assert(_v); return pow(m - 2); } else { auto eg = inv_gcd(_v, m); assert(eg.first == 1); return eg.second; } } friend constexpr mint operator+(mint lhs, mint rhs) { return lhs += rhs; } friend constexpr mint operator-(mint lhs, mint rhs) { return lhs -= rhs; } friend constexpr mint operator*(mint lhs, mint rhs) { return uint64_t(lhs._v) * rhs._v; } friend constexpr mint operator/(mint lhs, mint rhs) { return lhs /= rhs; } friend constexpr bool operator==(mint lhs, mint rhs) { return lhs._v == rhs._v; } friend constexpr bool operator!=(mint lhs, mint rhs) { return lhs._v != rhs._v; } friend istream& operator>>(istream& in, mint& x) { long long a; in >> a; x = a; return in; } friend ostream& operator<<(ostream& out, const mint& x) { return out << x.val(); } private: uint32_t _v = 0; static constexpr bool prime = []() -> bool { if(m == 1) return 0; if(m == 2 or m == 7 or m == 61) return 1; if(m % 2 == 0) return 0; uint32_t d = m - 1; while(d % 2 == 0) d /= 2; for(uint32_t a : {2, 7, 61}) { uint32_t t = d; mint y = mint(a).pow(t); while(t != m - 1 && y != 1 && y != m - 1) { y *= y; t <<= 1; } if(y != m - 1 && t % 2 == 0) return 0; } return 1; }(); static constexpr pair<int32_t, int32_t> inv_gcd(int32_t a, int32_t b) { if(a == 0) return {b, 0}; int32_t s = b, t = a, m0 = 0, m1 = 1; while(t) { const int32_t u = s / t; s -= t * u; m0 -= m1 * u; swap(s, t); swap(m0, m1); } if(m0 < 0) m0 += b / s; return {s, m0}; } }; using modint998244353 = StaticModint<998244353>; using modint1000000007 = StaticModint<1000000007>; using mint = modint998244353; int main(void) { ll n, m; cin >> n >> m; ll cur = n; mint ans = 0; rep(d, 0, 1000000) { ll l = min(cur, m / (d + 1)); ans += mint(m) * (cur - l) - mint(d) * (cur + l + 1) * (cur - l) / 2; cur = l; } rep(i, 1, cur + 1) { ans += m % i; } cout << ans << '\n'; }