結果
問題 | No.2891 Mint |
ユーザー | k1suxu |
提出日時 | 2024-09-13 22:43:06 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 392 ms / 2,000 ms |
コード長 | 7,395 bytes |
コンパイル時間 | 4,175 ms |
コンパイル使用メモリ | 269,912 KB |
実行使用メモリ | 54,064 KB |
最終ジャッジ日時 | 2024-09-13 22:43:21 |
合計ジャッジ時間 | 12,045 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 3 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 68 ms
53,668 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 392 ms
52,568 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,944 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 297 ms
52,868 KB |
testcase_18 | AC | 173 ms
28,060 KB |
testcase_19 | AC | 159 ms
28,328 KB |
testcase_20 | AC | 265 ms
53,384 KB |
testcase_21 | AC | 153 ms
28,284 KB |
testcase_22 | AC | 324 ms
53,412 KB |
testcase_23 | AC | 119 ms
27,924 KB |
testcase_24 | AC | 288 ms
53,644 KB |
testcase_25 | AC | 359 ms
54,064 KB |
testcase_26 | AC | 342 ms
52,472 KB |
testcase_27 | AC | 323 ms
52,680 KB |
testcase_28 | AC | 369 ms
52,952 KB |
testcase_29 | AC | 164 ms
29,260 KB |
testcase_30 | AC | 275 ms
53,620 KB |
testcase_31 | AC | 174 ms
29,124 KB |
testcase_32 | AC | 302 ms
52,752 KB |
testcase_33 | AC | 220 ms
53,732 KB |
testcase_34 | AC | 236 ms
53,196 KB |
testcase_35 | AC | 267 ms
52,600 KB |
testcase_36 | AC | 288 ms
52,848 KB |
testcase_37 | AC | 56 ms
52,796 KB |
testcase_38 | AC | 53 ms
53,112 KB |
testcase_39 | AC | 59 ms
53,184 KB |
testcase_40 | AC | 62 ms
53,292 KB |
testcase_41 | AC | 34 ms
28,692 KB |
testcase_42 | AC | 2 ms
6,940 KB |
testcase_43 | AC | 2 ms
6,940 KB |
testcase_44 | AC | 2 ms
6,940 KB |
testcase_45 | AC | 2 ms
6,940 KB |
testcase_46 | AC | 2 ms
6,940 KB |
testcase_47 | AC | 59 ms
53,056 KB |
testcase_48 | AC | 60 ms
53,708 KB |
testcase_49 | AC | 67 ms
54,060 KB |
testcase_50 | AC | 26 ms
29,216 KB |
testcase_51 | AC | 55 ms
53,700 KB |
testcase_52 | AC | 21 ms
16,860 KB |
testcase_53 | AC | 47 ms
52,952 KB |
testcase_54 | AC | 51 ms
53,524 KB |
testcase_55 | AC | 15 ms
16,600 KB |
testcase_56 | AC | 65 ms
53,144 KB |
ソースコード
#pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i = 0; i < (int)n; i++) #define FOR(n) for(int i = 0; i < (int)n; i++) #define repi(i,a,b) for(int i = (int)a; i < (int)b; i++) #define all(x) x.begin(),x.end() //#define mp make_pair #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define vvvvi vector<vvvi> #define pii pair<int,int> #define vpii vector<pair<int,int>> template<typename T> bool chmax(T &a, const T b) {if(a<b) {a=b; return true;} else {return false;}} template<typename T> bool chmin(T &a, const T b) {if(a>b) {a=b; return true;} else {return false;}} using ll = long long; using ld = long double; using ull = unsigned long long; const ll INF = numeric_limits<long long>::max() / 2; const ld pi = 3.1415926535897932384626433832795028; const ll mod = 998244353; int dx[] = {1, 0, -1, 0, -1, -1, 1, 1}; int dy[] = {0, 1, 0, -1, -1, 1, -1, 1}; #define int long long template<long long MOD> struct Modular_Int { using Mint_Type = Modular_Int<MOD>; long long x; Modular_Int() = default; Modular_Int(long long x_) : x(x_ >= 0? x_%MOD : (MOD-(-x_)%MOD)%MOD) {} long long val() const { return (x%MOD+MOD)%MOD; } static long long get_mod() { return MOD; } Mint_Type& operator^=(long long d) { Mint_Type ret(1); long long nx = x; while(d) { if(d&1) ret *= nx; (nx *= nx) %= MOD; d >>= 1; } *this = ret; return *this; } Mint_Type operator^(long long d) const {return Mint_Type(*this) ^= d;} Mint_Type pow(long long d) const {return Mint_Type(*this) ^= d;} //use this basically Mint_Type inv() const { return Mint_Type(*this) ^ (MOD-2); } //only if the module number is not prime //Don't use. This is broken. // Mint_Type inv() const { // long long a = (x%MOD+MOD)%MOD, b = MOD, u = 1, v = 0; // while(b) { // long long t = a/b; // a -= t*b, swap(a, b); // u -= t*v, swap(u, v); // } // return Mint_Type(u); // } Mint_Type& operator+=(const Mint_Type other) { if((x += other.x) >= MOD) x -= MOD; return *this; } Mint_Type& operator-=(const Mint_Type other) { if((x -= other.x) < 0) x += MOD; return *this; } Mint_Type& operator*=(const Mint_Type other) { long long z = x; z *= other.x; z %= MOD; x = z; if(x < 0) x += MOD; return *this; } Mint_Type& operator/=(const Mint_Type other) { return *this = *this * other.inv(); } Mint_Type& operator++() { x++; if (x == MOD) x = 0; return *this; } Mint_Type& operator--() { if (x == 0) x = MOD; x--; return *this; } Mint_Type operator+(const Mint_Type other) const {return Mint_Type(*this) += other;} Mint_Type operator-(const Mint_Type other) const {return Mint_Type(*this) -= other;} Mint_Type operator*(const Mint_Type other) const {return Mint_Type(*this) *= other;} Mint_Type operator/(const Mint_Type other) const {return Mint_Type(*this) /= other;} Mint_Type& operator+=(const long long other) {Mint_Type other_(other); *this += other_; return *this;} Mint_Type& operator-=(const long long other) {Mint_Type other_(other); *this -= other_; return *this;} Mint_Type& operator*=(const long long other) {Mint_Type other_(other); *this *= other_; return *this;} Mint_Type& operator/=(const long long other) {Mint_Type other_(other); *this /= other_; return *this;} Mint_Type operator+(const long long other) const {return Mint_Type(*this) += other;} Mint_Type operator-(const long long other) const {return Mint_Type(*this) -= other;} Mint_Type operator*(const long long other) const {return Mint_Type(*this) *= other;} Mint_Type operator/(const long long other) const {return Mint_Type(*this) /= other;} bool operator==(const Mint_Type other) const {return (*this).val() == other.val();} bool operator!=(const Mint_Type other) const {return (*this).val() != other.val();} bool operator==(const long long other) const {return (*this).val() == other;} bool operator!=(const long long other) const {return (*this).val() != other;} Mint_Type operator-() const {return Mint_Type(0LL)-Mint_Type(*this);} //-1: sqrtが存在しない //複数存在する場合どれを返すかは不明 long long get_sqrt() const { long long a = val(), p = get_mod(); if(a == 0) return 0; if(p == 2) return a; if(Mint_Type(a).pow((p - 1) >> 1).val() != 1) return -1; long long b = 1; while(Mint_Type(b).pow((p - 1) >> 1).val() == 1) ++b; long long e = 0, m = p - 1; while(m % 2 == 0) m >>= 1, ++e; long long x = Mint_Type(a).pow((m - 1) >> 1).val(); long long y = a * (x * x % p) % p; (x *= a) %= p; long long z = Mint_Type(b).pow(m).val(); while(y != 1) { long long j = 0, t = y; while(t != 1) { j += 1; (t *= t) %= p; } z = Mint_Type(z).pow((long long)1 << (e - j - 1)).val(); (x *= z) %= p; (z *= z) %= p; (y *= z) %= p; e = j; } return x; } template <typename T> friend Mint_Type operator+(T t, const Mint_Type& o) { return o + t; } template <typename T> friend Mint_Type operator-(T t, const Mint_Type& o) { return -o + t; } template <typename T> friend Mint_Type operator*(T t, const Mint_Type& o) { return o * t; } template <typename T> friend Mint_Type operator/(T t, const Mint_Type& o) { return o.inv() * t; } }; // TODO: SELECT MOD_VAL // const long long MOD_VAL = 1e9+7; const long long MOD_VAL = 998244353; using mint = Modular_Int<MOD_VAL>; istream& operator>>(istream& is, mint& x) { long long X; is >> X; x = X; return is; } ostream& operator<<(ostream& os, mint& x) { os << x.val(); return os; } // 1e9 + 7をmodとして使いたいときに注意!!!!特にCFやCCなどのAtCoder以外 //first: floor(N/[l,r]), second: [l,r](閉区間) vector<pair<long long, pair<long long, long long>>> floor_quotient_ranges(long long N){ vector<pair<long long, pair<long long, long long>>> ans; for (long long i = 1; i * i <= N; i++){ ans.push_back(make_pair(N / i, make_pair(i, i))); } for (long long i = N / ((long long) sqrt(N) + 1); i >= 1; i--){ ans.push_back(make_pair(i, make_pair(N / (i + 1) + 1, N / i))); } return ans; } mint range_sum(int l, int r) { return mint(l) * (r-l+1) + mint(r-l) * (r-l+1) / 2; } void solve() { int n, m; cin >> n >> m; vector<pair<int, pii>> qrange = floor_quotient_ranges(m); mint ans = 0; for(auto e : qrange) if(e.second.first <= n) ans += mint(m) * (min(n, e.second.second) - e.second.first + 1) - e.first * range_sum(e.second.first, min(n, e.second.second)); ans += mint(m) * max(0LL, n-m); cout << ans.val() << endl; } signed main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; }