题目描述
Nobody comes to Vlatko’s office hours anymore. Angered, enraged and disgruntled, Vlatko’s revenge is a convenient task for COCI:
You are given an infinite arithmetic sequence A(n) = Cn + D, defined for all natural numbers n. We want find a sequence of M distinct natural numbers n1, n2, ..., nM less than or equal to 1015 such that the corresponding members of sequence A(n1), A(n2), ..., A(nM) all have the same sum of digits in base B.
Please note: Every positive integer N can be written in base B as follows: create the unique string xkxk-1...x1x0, where 0 ≤ xi < B for each i, and the equation xkBk + xk-1Bk-1 + ... + x1B + x0 = N is satisfied. The sum of digits is given with xk + ... + x0.
题目翻译
再也没有人来 Vlatko 的办公时间了。 愤怒、愤怒和不满，Vlatko 的复仇对 COCI 来说是一项方便的任务：
给定一个无限算术序列 A(n) = Cn + D，为所有自然数 n 定义。 我们想要找到一个由 M 个不同的自然数组成的序列$ n_1, n_2, ..., n_M $小于或等于 $10^{15}$，使得序列 A($n_1$), A($n_2$), ..., A($n_M$) 的对应成员 都在底数 B 中具有相同的数字总和。
请注意：每个正整数 N 都可以以 B 为底写成：创建唯一的字符串$ x_kx_{k-1}...x_1x_0$，其中$ 0 ≤ x_i < B $对于每个 i，以及等式 $x_kB_k + x_{k-1}B_{k-1} + . .. + x_1B + x_0 = N$ 满足。 数字总和由$ x_k + ... + x_0$ 给出。
INPUT
The first line of input contains four integers C, D, B and M (1 ≤ C, D ≤ 10000, 2 ≤ B ≤ 5000, 1 ≤ M ≤ 250000).
OUTPUT
The first and only line of output must contain the required numbers, separated by spaces, in an arbitrary order.
Please note: you must output the numbers ni, not numbers A(ni). All numbers in the output should be less than or equal to $10^{15}$.
The input data will be such that a solution that meets the given conditions exists.
样例 #1
样例输入 #1
5 3 2 2样例输出 #1
2 5样例 #2
样例输入 #2
2 1 10 3样例输出 #2
2 20 200测试用例的说明
在第一个测试用例中，一个可能的序列是输出中的序列。
等差数列的对应成员是 5* 2 + 3 = 13 和 5* 5 + 3 = 28。
以 2 为底的数字 13 的格式为 1101，而以 2 为底的数字 28 的格式为 11100。
两种格式的数字都等于 3。
在第二个测试用例中，序列的对应成员是 2 *2 + 1 = 5、2 * 20 + 1 = 41 和 2 *200 + 1 = 401。
数字的位数，以 10 为基数，总和为 5。