問題一覧 > 通常問題

No.3118 Increment or Multiply

レベル : / AI推定難易度 : 1775 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 64
作問者 : Naru820 / テスター : kenken714 ponjuice Nzt3
お気に入りにしたユーザー ProblemId : 12087 / 自分の提出
問題文最終更新日: 2025-11-16 05:52:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
CPCTF 2025 : PPC (順位表) の他の問題:

Problem Statement

You are given positive integers $N,A$. For a positive integer $K$ less than or equal to $N$, consider the following "problem" and let $f(K)$ be its answer.

Problem

There is a variable $C$, initially $C = K$. In $1$ operation, you can either add $1$ to $C$ or multiply it by $A$.

Find the minimum number of operations required to make $C = N$.

Find the sum of $f(K)$ over all positive integers $K$ less than or equal to $N$, that is, the value of $\displaystyle \sum_{i = 1}^{N}f(i)$, modulo $998244353$.

There are $T$ test cases in total.

Constraints

  • $1 \leq T \leq 10^{4}$
  • $1 \leq N \leq 10^{18}$
  • $1 \leq A \leq 10^{18}$

Input

The input is given from standard input in the following format. 
$T$
$\text{case}_{1}$
$\text{case}_2$
$\ldots$
$\text{case}_{T}$

Here, $\text{case}_i$ denotes the $i$-th test case.

Each test case is given in the following format.

$N\ A$

Output

Print $T$ lines. On the $j (1 \leq j \leq T)$-th line, print the value of $\displaystyle \sum _{i = 1}^{N}f(i)$ for $\text{case}_j$ modulo $998244353$, followed by a newline.

Sample

Sample 1
Input
3
5 2
1 1
271828459045235602 314159265358979323
Output
8
0
487598590

This input contains $3$ test cases. We explain the $1$-st test case.

We have $f(1) = 3$. This is because multiplying $1$ by $2$ $2$ times and then adding $1$ turns $1$ into $5$ in $3$ operations, and it can be proven that $1$ cannot be turned into $5$ in $2$ or fewer operations.

By similar reasoning, we have $f(2) = 2$,$f(3) = 2$,$f(4) = 1$,$f(5) = 0$.

Their sum is $3+2+2+1+0 = 8$, so the answer to the 1st test case is $8$. Therefore, print $8$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。