結果
問題 | No.2891 Mint |
ユーザー | 矢澤式WINTER |
提出日時 | 2024-09-13 23:43:17 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 487 ms / 2,000 ms |
コード長 | 2,370 bytes |
コンパイル時間 | 5,455 ms |
コンパイル使用メモリ | 310,516 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-13 23:43:29 |
合計ジャッジ時間 | 12,475 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 54 |
ソースコード
#include <bits/stdc++.h> using namespace std; //*/ #include <atcoder/all> using namespace atcoder; // //*/ // #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // #pragma GCC target("avx,avx2,fma") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #define rep(i,n) for(int i=0;i<n;i++) #define Rep(i,a,b) for(int i=a;i<b;i++) #define ALL(x) (x).begin(),(x).end() #define dbgv(x); for(auto now : x) cout << now << " "; cout << endl; //using P = pair<int,int>; using ll = long long; using ull = unsigned long long; //*/ template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<int> vint; random_device rnd; mt19937 rng(rnd()); using mint = modint998244353; mint su(mint x){ return x*(x+1)/2; } void solve(){ ll n,m; cin >> n >> m; mint ans = 0; ll now = 1,nxt = 0; // if(m/n == 0){ // ans = m; // ans *= n; // cout << ans.val() << endl; // return; // } for(ll i = 1;i <= n;i++){ if(m/i <= 50000){ now = i; break; } ans += (mint)(m%i); if(i == n){ cout << ans.val() << endl; return; } //cout << m%i << endl; } mint coef = (n-now+1); auto f = [&](ll x)->ll{ ll p = m/x; if(p == m/n) return n+1; ll wa = n+1,ac = x; while(wa-ac > 1){ ll mid = (wa+ac)/2; if(m/mid < p) wa = mid; else ac = mid; } return wa; }; while(now != n+1){ nxt = f(now); //cerr << now << " " << nxt << endl; mint diff = (mint)(m/now); //cerr << diff.val() << endl; diff *= (su((mint)(nxt-1))-su((mint)(now-1))); ans -= diff; swap(now,nxt); } m %= 998244353; coef *= m; ans += coef; cout << ans.val() << endl; // mint test = 0; // for(int i = 1;i <= n;i++) test += (mint)(m%i); // cout << test.val() << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; rep(testcase,t) solve(); }