問題一覧 > 通常問題

No.2032 Let's Write Multiples!!

レベル : / AI推定難易度 : 2050 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 33
作問者 : Shirotsume / テスター : ygussany とりゐ
お気に入りにしたユーザー ProblemId : 8259 / 自分の提出
問題文最終更新日: 2022-08-05 19:51:40
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
yukicoder contest 355 (順位表) の他の問題:

Problem Statement

Suppose that all multiples of $K$ between $L$ and $R$, inclusive, are written out in decimal notation, each exactly $1$ time. Find the number of times the digit $C$ is written.

You are given $T$ test cases; solve each of them.

Constraints

  • All input values are integers.
  • $1 \leq T \leq 5 \times 10^4$
  • $1 \leq L \leq R < 10^9$
  • $1 \leq K < 10^9$
  • $1 \leq C \leq 9$

Input

The input is given from standard input. Line $1$ is given in the following format.

$T$

Then, $T$ test cases follow, each given in the following format.

$L$ $R$ $K$ $C$

Output

Print $T$ lines. On line $i$ $(1 \leq i \leq T)$, print the answer to the $i$-th test case.

Print a newline at the end.

Sample

Sample 1
Input
6
30 39 3 3
1 99 100 1
123456789 234567890 2 3
999 9999999 999 9
3141592 653589793 238462 6
1 999999999 1 7
Output
5
0
40827156
7043
2704
900000000

$6$ cases are given.

For test case $1$, the multiples of $3$ between $30$ and $39$, inclusive, are $30, 33, 36, 39$. Thus, the digit $3$ is written $5$ times in total.

For test case $2$, there are no multiples of $100$ between $1$ and $99$, inclusive, so not even $1$ number is written. Thus, the digit $1$ is written $0$ times.

For test case $3$, when all multiples of $2$ between $123456789$ and $234567890$, inclusive, are written, the digit $3$ is written $40827156$ times.

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