Fraction
Time limit1sMemory limit1024 MB
For each query, print n decimal digits of a/b starting at the i-th digit after the decimal point, using the terminating representation when two exist.
- Level
Medium6 of 10
- Topics
- Math, Number theory, Implementation, Prefix sum
- Solved
- No attempts yet
Problem
Given an arbitrary integer i, a number is called a "computable number" if an algorithm exists that computes the i-th digit of that number, either above or below the decimal point.
If no such algorithm exists, the number is called an "uncomputable number". For example, the Chaitin constant, which represents the probability that a randomly generated program does not run forever, is an uncomputable number. No algorithm can compute this number to arbitrary precision.
Junseok wondered whether every fraction whose denominator and numerator are natural numbers is a computable number. Help Junseok by writing an algorithm that computes the i-th digit below the decimal point of a / b, proving that every rational number is computable.
Input
The first line gives the number of test cases T. (1 ≤ T ≤ 100)
The first line of each test case gives integers a and b, separated by a space. (1 ≤ a, b ≤ 1018)
The second line of each test case gives integers i and n, separated by a space. (1 ≤ i ≤ 1018, 1 ≤ n ≤ 100)
Output
For each test case, print the n digits of a / b in decimal form, from the i-th digit below the decimal point through the (i + n - 1)-th digit.
If several decimal representations are possible, choose the one with infinitely many zeros below the decimal point.