Problem E
Raising the Bar
Yraglac sells the finest swords in the land, which he fine-tunes to exact measurements. He engraves each sword’s exact measurements in fractions of a metre so that his customers know exactly what they’re getting. For example, his builds his most famous dagger to exactly one third of a meter in length so he engraves “$1/3\, \textrm{m}$” into the side of the blade.
His customers find the fractions a little hard to work with though and have requested that Yraglac adds the decimal expansion for each fraction. Since some fractions have infinite expansions, like how $1/3 = 0.333\ldots $, Yraglac can draw a bar overtop the part of the decimal that will repeat infinitely. For example, he’ll engrave $0.\overline{3}$ next to $1/3$ and $0.3\overline{571428}$ next to $5/14$.1
Engraving takes time, so Yraglac wants to know exactly how many digits he’ll need to write after the decimal point as part of the finite sequence, and how many digits to write as part of the infinitely repeating sequence underneath a bar. Can you help out Yraglac?
Input
Input consists of two integers $1 \leq n < d \leq 10^6$ on a single line, the numerator and denominator of a fraction corresponding to a sword measurement.
Output
Output two space-separated integers $f$, the number of digits in the finite sequence after the decimal point, and $i$, the number of digits in the infinite sequence after the finite sequence, for the decimal expansion corresponding to $n/d$.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 3 |
0 1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 14 |
1 6 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 2 |
1 0 |
Footnotes
- Yraglac knows that he can write finite decimal expansions as infinite expansions, since for example $0.5 = 0.5\overline{0} = 0.4\overline{9}$, but he would rather write the finite expansion in these cases since it takes less engraving.
