問題一覧 > 通常問題

No.2589 Prepare Integers

レベル : / AI推定難易度 : 2700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 9
作問者 : KumaTachiRen / テスター : hirayuu_yc
お気に入りにしたユーザー ProblemId : 9390 / 自分の提出
問題文最終更新日: 2024-01-01 00:13:56
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
Advent Calendar Contest 2023 (順位表) の他の問題:

Problem Statement

You are going to prepare integers for a Christmas party.

Initially, you have $10^{1000}$ copies of the integer $0$. You also own a machine that, when given $2$ non-negative integers $X,Y$, consumes them and produces the non-negative integer $Z$ determined as follows:

  • For any non-negative integer $i$, let $x,y$ be the digits at the $K^i$ place of $X,Y$ written in base $K$, respectively. Then the digit at the $K^i$ place of $Z$ written in base $K$ is $(x+y)\bmod K$ (where $K$ is an integer of at least $2$ given in the input).
An integer that can be made by using the machine any number of times (possibly $0$ times) on the integers you have is called a good number.

You are given $Q$ queries. Process them in the given order. Each query gives integers $t,x\ (1\leq t\leq 3)$.

  • If $t=1$: you newly obtain $10^{1000}$ copies of the positive integer $x$. This also affects subsequent queries; in particular, the set of good numbers may change before and after this query.
  • If $t=2$: print the $x$-th smallest value among the good numbers. If there are fewer than $x$ distinct good numbers, print -1 instead.
  • If $t=3$: print the number of good numbers that are at most $x$.

Input

$K\ Q$
$t_1\ x_1$
$\vdots$
$t_Q\ x_Q$

  • $2\leq K\leq 10^9$
  • $1\leq Q\leq 10^4$
  • $1\leq t_i\leq 3$
  • If $t_i=1$, then $1\leq x_i\leq 10^9$
  • If $t_i=2$, then $1\leq x_i\leq 10^{18}$
  • If $t_i=3$, then $0\leq x_i\leq 10^{18}$
  • All input values are integers.

Output

Let $M$ be the number of queries among the $Q$ queries whose $t$ is $2$ or $3$. Print $M$ lines.

On line $j\ (1\leq j\leq M)$, print the integer as instructed by the $j$-th query among those whose $t$ is $2$ or $3$.

Print a newline after the output on line $M$ as well.

Sample

Sample 1
Input
2 8
1 13
1 5
1 9
2 5
3 5
1 11
2 5
3 5
Output
8
4
4
6

After processing up to the $3$rd query, the good numbers are $0,1,4,5,8,9,12,13$. After processing up to the $6$th query, the good numbers are $0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15$.

Sample 2
Input
17 10
1 20
2 23
3 12
1 17
2 20
3 23
1 12
2 17
3 20
2 23
Output
-1
1
19
24
16
21
22

Sample 3
Input
30 10
1 68045
1 39072
1 14466
2 846282
3 472013
2 294767
1 37755
2 50526
3 710447
3 946027
Output
-1
7867
-1
505228
71046
81000

Sample 4
Input
100000000 10
1 280891310
1 866405535
2 507843655
3 7490561978746756
1 181882853
2 869882551
3 44425977686455401
1 843088846
2 395320008
3 5837034220072028
Output
5039218270
749056200000000
869882550
10000000000000000
395320007
5837034220072029

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