結果
問題 | No.3118 Increment or Multiply |
ユーザー |
|
提出日時 | 2025-03-20 11:47:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,174 bytes |
コンパイル時間 | 1,908 ms |
コンパイル使用メモリ | 193,916 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-12 16:42:41 |
合計ジャッジ時間 | 4,500 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 15 WA * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll mod = 998244353; constexpr ll twoinv = 499122177; #define fast cin.tie(nullptr); ios_base::sync_with_stdio(false) ll modpow(ll base, ll exp) { if (!exp) return 1; ll res = modpow(base, exp / 2); res = (res * res) % mod; if (exp % 2) res = (res * base) % mod; return res; } ll inv(ll x,ll mod){ return modpow(x,mod - 2); } ll digsum(ll n,ll a){ ll res = 0; while(n){ res += n % a; n /= a; } return res; } ll sum(ll n,ll a){ if(a == 1){ return ((((n % mod) * ((n - 1) % mod)) % mod) * twoinv) % mod; } ll k = 0,power = 1,ans = 0; while(power <= n){ ll f = (n / power) % mod + digsum(n % power,a) % mod + k; f %= mod; ans += f * ((n / power - n / (power*a))% mod) % mod; ans %= mod; if(power > n / a) break; power *= a; k++; } ll dec = (n% mod) * ((n + 1) %mod) % mod * twoinv % mod; return ((ans-dec)% mod + mod) % mod; } ll t,n,a; int main() { fast; cin >> t; while(t--){ cin >> n >> a; cout << sum(n,a) << endl; } }