結果
問題 | No.2127 Mod, Sum, Sum, Mod |
ユーザー |
![]() |
提出日時 | 2022-11-18 22:53:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 3,186 bytes |
コンパイル時間 | 2,060 ms |
コンパイル使用メモリ | 198,128 KB |
最終ジャッジ日時 | 2025-02-08 22:16:51 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#ifdef LOGX#define _GLIBCXX_DEBUG#endif#include <bits/stdc++.h>using namespace std;#include <atcoder/modint>using namespace atcoder;/*---------macro---------*/#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)#define unless(x) if(!(x))#define until(x) while(!(x))#define ALL(a) a.begin(),a.end()#define RALL(a) a.rbegin(),a.rend()#define mybit(i,j) (((i)>>(j))&1)/*---------type/const---------*/constexpr int big=1000000007;//constexpr int big=998244353;constexpr double EPS=1e-8; //適宜変えるtypedef long long ll;typedef unsigned long long ull;typedef std::string::const_iterator state; //構文解析constexpr int dx[4]={1,0,-1,0};constexpr int dy[4]={0,1,0,-1};constexpr char newl='\n';struct{constexpr operator int(){return -int(1e9)-10;}constexpr operator ll(){return -ll(1e18)-10;}}neginf;struct{constexpr operator int(){return int(1e9)+10;}constexpr operator ll(){return ll(1e18)+10;}constexpr auto operator -(){return neginf;}}inf;/*---------debug---------*/#ifdef LOGX#include <template/debug.hpp>#else#define dbg(...) ;#define dbgnewl ;#define prt(x) ;#define _prt(x) ;#endif/*---------function---------*/template<typename T> T max(const std::vector<T> &a){T ans=a[0];for(T elem:a){ans=max(ans,elem);}return ans;}template<typename T> T min(const std::vector<T> &a){T ans=a[0];for(T elem:a){ans=min(ans,elem);}return ans;}template<typename T,typename U> bool chmin(T &a,const U b){if(a>b){a=b;return true;}return false;}template<typename T,typename U> bool chmax(T &a,const U b){if(a<b){a=b;return true;}return false;}bool valid(int i,int j,int h,int w){return (i>=0 && j>=0 && i<h && j<w);}template<class T,class U>T expm(T x,U y,const ll mod=big){T res=1;while(y){if(y&1)(res*=x)%=mod;(x*=x)%=mod;y>>=1;}return res;}template<class T,class U>T exp(T x,U y){T res=1;while(y){if(y&1)res*=x;x*=x;y>>=1;}return res;}using mint=modint998244353;const mint inv2=499122177, inv6=166374059;//~(i-1)^2mint sum_2(ll i){return mint(i-1)*i*mint(2*i-1)*inv6;}//i^2~(j-1)^2mint sum_2(ll i,ll j){return sum_2(j)-sum_2(i);}//~i-1mint sum_1(ll i){return mint(i-1)*i*inv2;}mint sum_1(ll i,ll j){return sum_1(j)-sum_1(i);}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout << std::fixed << std::setprecision(10);/*------------------------------------*/ll n,m;cin >> n >> m;mint ans=0;ll j=1;for(;j*j<=n && j<=m;j++){ans+=mint(j)*mint(j-1)*inv2*(n/j);ans+=sum_1(n%j+1);///////////////////}//ここからはn/jが一定なものをまとめて。for(;j<=min(n,m);){ll k=n/j;ll nxt_j=n/k+1;chmin(nxt_j,min(n,m)+1);//[j,nxt_j)をみるans+=(sum_2(j,nxt_j) - sum_1(j,nxt_j))*inv2*(n/j);ans+=(mint(k)*k*sum_2(j,nxt_j)-(mint(2)*n*k+k)*sum_1(j,nxt_j)+(mint(n)*n+n)*mint(nxt_j-j))*inv2;/////////j=nxt_j;}assert(j==min(n,m)+1);//j=n+1~mの時、n%j=nif(m>n)ans+=mint(m-n)*n*(n+1)*inv2;//これをはやくするcout << ans.val() << endl;}