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

Remember to use this editorial 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: Plasmatic

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.
• Hard code every possible input.

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.

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

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.