No.3118 Increment or Multiply
タグ : / 解いたユーザー数 61
作問者 :
Naru820
/ テスター :
kenken714
ponjuice
Nzt3
問題文
正の整数 $N,A$ が与えられます。$N$ 以下の正の整数 $K$ に対して、以下の「問題」について考え、その答えを $f(K)$ とします。
問題
変数 $C$ があり、初め $C = K$ です。
あなたは $1$ 回の操作で $C$ に $1$ を足す、または $A$ を掛けることができます。
$C = N$ とするために必要な最小の操作回数を求めてください。
$N$ 以下の正の整数 $K$ 全てについての $f(K)$ の総和、すなわち $\displaystyle \sum_{i = 1}^{N}f(i)$の値を $998244353$ で割ったあまりを求めてください。
テストケースは全部で $T$ ケース与えられます。
制約
- $1 \leq T \leq 10^{4}$
- $1 \leq N \leq 10^{18}$
- $1 \leq A \leq 10^{18}$
入力
入力は、以下の形式で標準入力から与えられる。$T$
$\text{case}_{1}$
$\text{case}_2$
$\ldots$
$\text{case}_{T}$
ここで、$\text{case}_i$は$i$番目のテストケースを意味する。
各テストケースは以下の形式で与えられる。
$N\ A$
出力
$T$ 行出力せよ。$j (1 \leq j \leq T)$行目には、$\text{case}_j$ に対する $\displaystyle \sum _{i = 1}^{N}f(i)$ の値を $998244353$ で割ったあまりを出力し、最後に改行せよ。
サンプル
サンプル1
入力
3 5 2 1 1 271828459045235602 314159265358979323
出力
8 0 487598590
この入力にはテストケースが$3$つ含まれます。 $1$つ目のテストケースについて説明します。
$f(1) = 3$です。なぜなら、$1$に$2$を$2$回掛けた後、$1$を足せば$3$回の操作で$1$を$5$にでき、$2$回以下の操作で$1$を$5$にすることができないことが証明できるためです。
同様に考えると、 $f(2) = 2$,$f(3) = 2$,$f(4) = 1$,$f(5) = 0$です。
これらの和は、$3+2+2+1+0 = 8$なので、1つ目のテストケースに対する答えは$8$です。よって$8$を出力します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。