A1370. [COCI-2017_2018-contest6]#4 Kotrljanje
编程题
普及+/提高
知识点
题目描述
Vla-tko, Vla-tko, Vla-tko!
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 10^15 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 + ... + x
0.
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 10^15 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 + ... + x
0.
输入格式
The first line of input contains four integers C, D, B and M (1 ≤ C, D ≤ 10000, 2 ≤ B ≤ 5000, 1 ≤ M ≤ 250000).
输出格式
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^1
5.
The input data will be such that a solution that meets the given conditions exists.
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^1
5.
The input data will be such that a solution that meets the given conditions exists.
输入输出样例
输入 #1
5 3 2 2
输出 #1
2 5
输入 #2
2 1 10 3
输出 #2
2 20 200
说明/提示
Clarification of the test cases:
In the first test case, one of the possible sequences is the sequence in the output. The corresponding
members of the arithmetic sequence are 5 * 2 + 3 = 13 and 5 * 5 + 3 = 28. The format of number 13 in
base 2 is 1101, whereas the format of number 28 in base 2 is 11100. The sum of digits in both
formats is equal to 3.
In the second test case, the corresponding members of the sequence are 2 * 2 + 1 = 5, 2 * 20 + 1 =
41, and 2 * 200 + 1 = 401. Each of the numbers’ digits, written in base 10, sum up to 5.
In the first test case, one of the possible sequences is the sequence in the output. The corresponding
members of the arithmetic sequence are 5 * 2 + 3 = 13 and 5 * 5 + 3 = 28. The format of number 13 in
base 2 is 1101, whereas the format of number 28 in base 2 is 11100. The sum of digits in both
formats is equal to 3.
In the second test case, the corresponding members of the sequence are 2 * 2 + 1 = 5, 2 * 20 + 1 =
41, and 2 * 200 + 1 = 401. Each of the numbers’ digits, written in base 10, sum up to 5.