結果
問題 | No.1260 たくさんの多項式 |
ユーザー |
![]() |
提出日時 | 2020-10-17 16:07:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,476 bytes |
コンパイル時間 | 1,606 ms |
コンパイル使用メモリ | 167,884 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-21 02:51:34 |
合計ジャッジ時間 | 5,584 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 61 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define INF 1e18 typedef long long ll; typedef vector<ll> vec; typedef vector<vec> mat; const int inf = (int)1e9; //const ll N = 1000000007; const ll N = 998244353; ll inv(ll x,ll power) { ll res = 1; ll k = power; ll y = x%N; while (k) { if (k & 1)res = (res*y) % N; y = (y%N*y%N) % N; k /= 2; } return res; } int main(void){ ll n; cin>>n; ll I = 2; ll ans = 0; for(;I*I<=n;I++){ ll t = n; for(;;){ ans= (ans+t%I)%N; t=t/I; if(t<I){ ans=(ans+t)%N; break; } } } ll level = n; ll INV = inv(2LL,N-2); for(ll i=1;i<=I;i++){ //cout<<ans<<endl; ll t = n/i; if(t*t<=n)continue; if(i == 1){ ll s = n/(i+1); ll l = (level-s)%N; ans = (ans+l+N)%N; ll r1 = n%(level); ll r2 = n%(s+1); ll r = (r1+r2)%N; ll tmp = (l*r)%N; tmp = (tmp*INV)%N; ans = (ans+tmp)%N; level = s; continue; } ll s = n/(i+1); ll l = (level-s)%N; ans = ((l*i)%N+ans+N)%N; ll r1 = n%(level); ll r2 = n%(s+1); ll r = (r1+r2)%N; ll tmp = (l*r)%N; tmp = (tmp*INV)%N; ans = (ans+tmp)%N; ans = (ans+N)%N; level = s; } cout<<ans<<endl; return 0; }