結果
問題 |
No.3118 Increment or Multiply
|
ユーザー |
![]() |
提出日時 | 2025-04-19 23:47:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,026 bytes |
コンパイル時間 | 2,341 ms |
コンパイル使用メモリ | 193,496 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-19 23:47:19 |
合計ジャッジ時間 | 3,815 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 5 WA * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> PP; // #define MOD 1000000007 #define MOD 998244353 #define INF 2305843009213693951 #define PI 3.141592653589 #define setdouble setprecision #define REP(i,n) for(ll i=0;i<(n);++i) #define OREP(i,n) for(ll i=1;i<=(n);++i) #define RREP(i,n) for(ll i=(n)-1;i>=0;--i) #define ORREP(i,n) for(ll i=(n);i>=1;--i) #define rep(i,a,b) for(ll i=(a);i<=(b);++i) #define ALL(v) (v).begin(), (v).end() #define chmin(k,m) k = min(k,m) #define chmax(k,m) k = max(k,m) #define GOODBYE do { cout << "-1" << endl; return 0; } while (false) #define MM <<" "<< #define Endl endl ll greedy(ll N, ll A){ if(A==1 || A>N){ ll n = N%MOD; return (n*(n-1)/2)%MOD; } ll Ans = 0; OREP(i,N){ ll c = i; while(c*A <= N){ Ans++; c *= A; } Ans += N-c; } return Ans; } ll solve(ll N, ll A){ if(A==1 || A>N){ ll n = N%MOD; return (n*(n-1)/2)%MOD; } ll M = N; ll Ans = 0; ll P = 1; while(N>0){ ll nN = N/A; // y = M-N*P ll y = N%MOD; y = (y*P)%MOD; y = (M-y+MOD)%MOD; ll s = (N-nN)%MOD; Ans = (Ans+(y*s)%MOD)%MOD; ll w = s*(s-1)/2; w %= MOD; w = (w*P)%MOD; Ans = (Ans+w)%MOD; // cout << N MM nN MM y MM w << endl; N = nN; Ans += N;Ans%=MOD; P = (P*(A%MOD))%MOD; } return Ans; } int main(void){ //cin.tie(nullptr); //ios::sync_with_stdio(false); ll T; cin >> T; REP(_,T){ ll N,A; cin >> N >> A; ll Ans = solve(N,A); cout << Ans << endl; } // OREP(n,1000){ // OREP(a,1000){ // ll g = greedy(n,a); // ll s = solve(n,a); // if(g!=s){ // cout << n MM a << " " << g MM s << endl; // } // } // } return 0; }