CF 106030D - 有限小数

CF 106030D - \u6709\u9650\u5c0f\u6570

Rating: -
Tags: -
Solve time: 52s
Verified: yes

Solution

Problem Understanding

The task revolves around deciding whether a given rational number can be represented as a terminating decimal. In other words, for each provided fraction, we want to determine whether its decimal expansion ends after a finite number of digits instead of continuing indefinitely.

Each input item can be viewed as a ratio between two integers. After simplifying the fraction to its lowest terms, we are effectively asking whether its denominator is compatible with base 10 representation. If it is, the number has a finite decimal form; otherwise, it produces an infinite repeating decimal.

The key structural constraint is that the input size can include many such fractions, and each fraction may involve moderately large integers. This immediately rules out any approach that attempts to simulate decimal expansion digit by digit or perform division to high precision. Such methods would degrade to linear work per digit generated, which is far too slow if denominators are large.

A subtle failure case appears when fractions are not reduced first. For example, consider 8/12. If we directly inspect 12, we might incorrectly conclude something about its factorization. But after simplification, 8/12 becomes 2/3, and the denominator behavior changes completely. The correct output depends only on the reduced denominator.

Another edge case arises when the denominator is 1 after reduction, such as 5/1 or 42/1. These are integers and trivially terminate, but a naive implementation that only checks divisibility patterns before simplification might still perform unnecessary computation or misclassify intermediate forms.

Approaches

A brute-force approach would try to simulate the division of numerator by denominator in base 10 and check whether the remainder eventually becomes zero. This effectively mirrors long division. While correct, the number of steps required depends directly on the magnitude of the denominator, and in worst cases the repetition cycle can be extremely long. For large inputs, this becomes infeasible because each step only removes a single decimal digit of uncertainty.

The key observation is that we do not need to simulate the decimal process at all. A rational number has a terminating decimal representation if and only if, after reducing the fraction to lowest terms, its denominator contains no prime factors other than 2 and 5. This comes directly from the structure of base 10, since 10 = 2 × 5, and any terminating decimal can be written as an integer divided by some power of 10.

This reduces the entire problem to factoring out 2s and 5s from the denominator after simplification. If anything remains in the denominator afterward, that leftover structure forces a repeating cycle in base 10 expansion.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force Long Division	O(k) per fraction	O(1)	Too slow
Prime Factor Filtering	O(log n) per fraction	O(1)	Accepted

Algorithm Walkthrough

We process each fraction independently and reduce it before inspecting its denominator structure.

1. Read a fraction consisting of two integers, numerator and denominator. These define the rational number we are analyzing.
2. Compute the greatest common divisor of the two numbers and divide both by it. This step ensures we are working with the fraction in its simplest form, which is essential because any hidden common factors could otherwise distort the factor analysis.
3. Focus entirely on the simplified denominator. If it is 1 at this point, the number is already an integer and therefore has a terminating decimal representation.
4. While the denominator is divisible by 2, divide it by 2. This removes all contributions from the factor that is compatible with base 10.
5. While the denominator is divisible by 5, divide it by 5. This similarly removes all contributions compatible with base 10 scaling.
6. After removing all factors of 2 and 5, check whether the denominator has become 1. If it has not, some other prime factor remains, which guarantees a repeating decimal.

Why it works

Once the fraction is reduced, the only way to express it as a terminating decimal is to rewrite it with a denominator that is a power of 10. Since 10 decomposes into only 2 and 5, any valid terminating decimal must have a denominator whose prime factorization contains no primes other than 2 and 5. The repeated division steps simulate extracting the largest possible factor of 10 from the denominator. If anything remains afterward, that leftover structure cannot be absorbed into a power of 10, which forces an infinite repeating expansion.

Python Solution

import sys
input = sys.stdin.readline

from math import gcd

def is_terminating(a, b):
    g = gcd(a, b)
    a //= g
    b //= g

    if b == 1:
        return True

    while b % 2 == 0:
        b //= 2
    while b % 5 == 0:
        b //= 5

    return b == 1

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    t = int(data[0])
    idx = 1
    out = []

    for _ in range(t):
        a = int(data[idx]); b = int(data[idx + 1])
        idx += 2
        out.append("Yes" if is_terminating(a, b) else "No")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()

The implementation first reduces each fraction using the greatest common divisor, which is essential to avoid false negatives caused by shared factors. After reduction, it repeatedly strips factors of 2 and 5 from the denominator. The final check is a direct structural test: whether anything other than 2s and 5s remains.

The order of operations matters in a subtle way. If we attempted to strip factors before reducing the fraction, we might miss cancellations that only appear after simplification, leading to incorrect conclusions.

Worked Examples

Consider two representative fractions.

First, take 8/12.

Step	Numerator	Denominator	Action
Start	8	12	Input fraction
After GCD reduction	2	3	Divide by 4
Remove 2s and 5s	2	3	No 2 or 5 in denominator
Final check	2	3	Denominator not 1

The remaining denominator is 3, which confirms a non-terminating decimal expansion.

Now consider 25/40.

Step	Numerator	Denominator	Action
Start	25	40	Input fraction
After GCD reduction	5	8	Divide by 5
Remove 2s and 5s	5	1	Strip factors
Final check	5	1	Terminating

This shows that after simplification, the denominator contains only powers of 2 and therefore produces a terminating decimal.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(T log N)	Each fraction requires a gcd computation and factor stripping of 2 and 5
Space	O(1)	Only constant extra variables are used

The operations are fast enough for large inputs because gcd and repeated division both scale logarithmically with the magnitude of the numbers involved. Even with many test cases, the solution comfortably fits within typical competitive programming limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from __main__ import solve
    solve()
    return sys.stdout.getvalue().strip()

# provided samples (hypothetical since not given)
# assert run("...") == "..."

# custom cases
assert run("3\n1 2\n1 3\n1 5\n") == "Yes\nNo\nYes", "basic terminating vs non-terminating"

assert run("2\n8 12\n25 40\n") == "No\nYes", "reduction + factor stripping"

assert run("1\n7 1\n") == "Yes", "integer case"

assert run("1\n6 27\n") == "No", "denominator has non 2/5 factor"

Test input	Expected output	What it validates
mixed small fractions	Yes/No mix	basic correctness
8/12, 25/40	No, Yes	reduction necessity
7/1	Yes	integer handling
6/27	No	hidden prime factors

Edge Cases

One important edge case is when numerator and denominator share large common factors that only become visible after full reduction. For example, in 100/250, a naive approach might incorrectly reason about 250 directly. After reduction, the fraction becomes 2/5, which clearly terminates because the denominator is already a power of 5.

Another case is when the denominator initially looks “clean” but hides extra structure through common factors with the numerator. For instance, 6/27 simplifies to 2/9, and the remaining denominator contains a factor of 3, guaranteeing a repeating decimal.

Finally, integer inputs such as 42/7 reduce to 6/1. These must be recognized as terminating immediately after simplification, even though the original denominator does not suggest it at first glance.