## Editorial for CPC '21 Contest 1 P1 - AQT and Fractions

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

#### Subtask 1

The number of possible inputs is very small in this subtask. Here are some solutions:

- The only time when the digits infinitely repeat is when and , so we can just check for this specific case and use something like the
`to_string(int)`

method in C++ to count the number of digits past the decimal. - Hardcode every possible input.

#### Subtask 2

is always a multiple of , so the decimal will never repeat infinitely, so we can convert the fraction to a string and just check the number of digits. Note that we cannot simply just count the number of digits in , as the fraction may not be completely reduced. Make sure to be careful about precision (i.e. using arbitrary precision integers).

**Time Complexity:** per test case.

#### Subtask 3

This subtask exists to reward solutions that would get full marks but fail due to precision or overflow errors.

#### Subtask 4

One possible solution is to observe that a finite decimal value for can only get so long with the input constraints, so we can perform long division to find the value of and assume that the answer is infinite if our decimal gets too long.

**Time Complexity:** per test case.

Alternatively, start by assuming that is **fully reduced** (if it is not the case, reduce the fraction first). Next, notice the following:

- The only way for the decimal to be finite is if for some where .
- Again let where and . The number of digits to the right of the decimal is always . We can show that this is true with the following:
- Let and . We can rewrite as and notice that either or (or both).
- Every power of (the portion) adds additional digit by 'shifting' the current decimal to the right.
- Every additional power of or (either or respectively) will always increase the number of digits by as the fraction is already reduced.
- Thus, if the number of digits is , otherwise the number of digits is , which is equivalent to .

Overall, this solution leads to a simpler implementation.

**Time Complexity:** per test case.

## Comments

Could someone explain why

dividing by 2 or 5 increases the digits after the decimal point by 1? (given that the original number without the decimal point has no factor of 2 or 5)If there were just one non-zero digit after the decimal point, I could see why this would be true, since I could literally just test out the possible digits.

But I can't seem to convince myself of this when multiple non-zero digits are involved; for example, I know that if we have 0.01 divided by 2 the 1 gets "halved" and we get 0.005; but where x is a placeholder for some nonzero digit, if we divide x.x1 by 2, the 1 getting "halved" contributes a 0.005, but the other nonzero digits also get "halved," so what's to keep those contributions from adding enough to the thousandths place that the last 5 ticks up to a bigger (more to the left) place? [I hope that made sense lol]