CF 102697120 - What the Frac (Easier Version)

Rating: -
Tags: -
Solve time: 1m 20s
Verified: yes

Solution

Problem Understanding

We are given one positive fraction written as a/b. The numerator a does not have to be smaller than the denominator b, so improper fractions such as 72/48 are valid. The only restriction relevant to the output is that a is not a multiple of b, so the original fraction cannot already represent a whole number.

The task is to remove every common factor shared by the numerator and denominator. If the greatest common divisor of a and b is g, then dividing both parts by g gives the unique simplest form a/g over b/g.

The published statement does not give explicit numerical upper bounds for a and b. Instead, it says that the input is small enough for a brute-force solution that tries possible factors to run efficiently. That makes a direct search acceptable for the easier version, but there is still a cleaner solution: the greatest common divisor can be found with Euclid's algorithm in logarithmic time. Since the input contains only one fraction, even a very small constant factor matters more than data structure choices.

There are several cases where a careless implementation can fail. For 6/8, the correct output is 3/4. A program that only checks whether a is divisible by b would leave the fraction unchanged, because 6 is not divisible by 8, even though both numbers have a common factor of 2.

For 72/48, the correct output is 3/2. The numerator is larger than the denominator, but that has no effect on simplification. A solution that assumes the numerator must be smaller could incorrectly reject the input or use the wrong search range.

For 37/73, the correct output is 37/73. The two numbers are coprime, so there is nothing to reduce. A solution that always divides by some factor without first checking that it divides both numbers would change the value of the fraction.

An input such as 6/2 is not a valid test case because the statement guarantees that the numerator is not a multiple of the denominator. Similarly, a = b is excluded because then the numerator is a multiple of the denominator. A test generator should respect those guarantees rather than treating such inputs as ordinary edge cases.

Approaches

The most direct approach is to search for common factors. We can inspect every integer d from 2 through min(a, b), and whenever d divides both numbers, divide both by it. Repeating this until no factor remains eventually produces a fraction whose numerator and denominator have no common divisor greater than 1, so the result is correct.

The drawback is that this method can perform one divisibility test for essentially every integer up to the smaller input. If m = min(a, b), scanning the full range performs m - 1 candidate checks in the worst case. The easier version explicitly guarantees that the numbers are small enough for such a brute-force method, which is why that approach is viable here.

There is a more fundamental way to phrase the same task. We do not actually need to discover every common factor separately. We only need their product, which is exactly the greatest common divisor of the numerator and denominator. The Euclidean algorithm computes this value without enumerating its possible divisors.

The key observation is that for positive integers a and b, replacing the pair with (b, a mod b) does not change their greatest common divisor. Every common divisor of a and b also divides a - qb, and a mod b is exactly a - qb for an appropriate integer q. Repeating this transformation eventually reaches a remainder of zero, and the last nonzero value is the GCD.

The brute-force method works because trying all possible factors eventually finds every common divisor. It fails to scale because it spends time examining factors that have no chance of being relevant. The observation that all common factors can be represented by one number, the GCD, reduces the entire simplification to one Euclidean algorithm followed by two divisions.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(min(a, b))	O(1)	Accepted for the easier constraints
Optimal	O(log(min(a, b)))	O(1)	Accepted

Algorithm Walkthrough

Read the fraction as a string and split it at /. The two resulting pieces are the numerator a and denominator b.
Compute g = gcd(a, b) using the Euclidean algorithm. The value g is exactly the largest positive integer that can divide both parts without changing the value of the fraction.
Divide both a and b by g. Since g divides both numbers, the resulting values are integers, and they have no common factor greater than 1.
Print the reduced numerator and denominator in the original a/b format. No conversion to a decimal is performed because the required answer is an exact fraction.

Why it works: throughout the Euclidean algorithm, the set of common divisors of the current pair does not change. When the second value becomes zero, every number divides zero, so the remaining first value is the greatest common divisor of the original numerator and denominator. Dividing both parts by that value removes their entire common factor, leaving two coprime integers. A fraction with coprime numerator and denominator is precisely its simplest form.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    s = input().strip()
    a, b = map(int, s.split('/'))

    x, y = a, b
    while y != 0:
        x, y = y, x % y

    g = x
    print(f"{a // g}/{b // g}")

if __name__ == "__main__":
    solve()

The input is kept as a string initially because the slash is part of the input format. Splitting on / gives exactly the two integers needed for the calculation.

The loop implements Euclid's algorithm directly. After each iteration, the pair changes from (x, y) to (y, x % y). The loop stops when y becomes zero, at which point x is the GCD.

The divisions happen only after the GCD has been found. This is preferable to repeatedly dividing during the search because it avoids changing the values whose common divisor we are trying to characterize.

Python integers do not overflow for the given problem, and the solution uses constant auxiliary memory. There is also no off-by-one issue in the optimal algorithm because Euclid's algorithm does not enumerate possible factors.

Worked Examples

Sample 1

Input:

6/8

The Euclidean algorithm proceeds as follows.

x	y	x % y
6	8	6
8	6	2
6	2	0

The last nonzero value is 2, so g = 2. Dividing both parts by 2 gives 3/4.

Original numerator	Original denominator	GCD	Reduced numerator	Reduced denominator
6	8	2	3	4

The output is:

3/4

This example exercises the central operation of the algorithm: a common factor exists, and it must be removed from both sides.

Sample 2

Input:

72/48

The Euclidean algorithm is:

x	y	x % y
72	48	24
48	24	0

The GCD is 24. Dividing gives 72 / 24 = 3 and 48 / 24 = 2.

Original numerator	Original denominator	GCD	Reduced numerator	Reduced denominator
72	48	24	3	2

The output is:

3/2

This trace confirms that the algorithm does not assume the fraction is proper. The numerator can remain larger than the denominator after simplification.

Sample 3

Input:

37/73

The Euclidean algorithm is:

x	y	x % y
37	73	37
73	37	36
37	36	1
36	1	0

The GCD is 1, so neither side can be reduced.

Original numerator	Original denominator	GCD	Reduced numerator	Reduced denominator
37	73	1	37	73

The output remains:

37/73

This is the coprime case. It also demonstrates why the algorithm must allow the GCD to be 1 rather than assuming some reduction is always possible.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log(min(a, b)))	Euclid's algorithm reduces the pair rapidly through remainders.
Space	O(1)	Only the numerator, denominator, GCD state, and a few temporary integers are stored.

The statement describes the easier version as having inputs small enough for brute force, so the optimal solution is comfortably within the one-second time limit and 256 MB memory limit. Its logarithmic running time is much stronger than the required bound and also remains efficient if the input values are substantially larger than the intended easier-version range.

Test Cases

The official samples are included below. The custom cases focus on a fraction that is already reduced, a fraction with a large common factor, a case where the numerator is larger than the denominator, and a large coprime pair.

import sys
import io

def solve():
    s = input().strip()
    a, b = map(int, s.split('/'))

    x, y = a, b
    while y != 0:
        x, y = y, x % y

    g = x
    print(f"{a // g}/{b // g}")

def run(inp: str) -> str:
    global input
    old_stdin = sys.stdin
    old_input = input

    sys.stdin = io.StringIO(inp)
    input = sys.stdin.readline

    try:
        solve()
        return sys.stdout.getvalue()
    finally:
        sys.stdin = old_stdin
        input = old_input

# The helper above needs captured stdout, so use a corrected version for testing.
def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    try:
        solve()
        return sys.stdout.getvalue()
    finally:
        sys.stdin = old_stdin
        sys.stdout = old_stdout

# Provided samples
assert run("6/8\n") == "3/4\n", "sample 1"
assert run("72/48\n") == "3/2\n", "sample 2"
assert run("37/73\n") == "37/73\n", "sample 3"

# Custom cases
assert run("1/2\n") == "1/2\n", "minimum-size coprime fraction"
assert run("100/80\n") == "5/4\n", "large common factor"
assert run("81/54\n") == "3/2\n", "reduction with numerator larger than denominator"
assert run("99991/99989\n") == "99991/99989\n", "large coprime values"

Test input	Expected output	What it validates
`1/2`	`1/2`	Smallest ordinary valid fraction and GCD equal to 1
`100/80`	`5/4`	Multiple common factors must be removed together
`81/54`	`3/2`	Improper fraction and nontrivial GCD
`99991/99989`	`99991/99989`	Large values with no reduction

The problem does not publish a numerical maximum for the input values, so the final custom case is a large stress case rather than a claimed exact maximum-size case. The important property is that the two values are coprime, forcing the algorithm to complete the Euclidean process without performing any simplification.

Edge Cases

For 6/8, the input is:

6/8

Euclid's algorithm produces gcd(6, 8) = 2. The algorithm divides both values by 2, giving 3/4. A naive solution that only looks for one number dividing the numerator but forgets to require divisibility of the denominator could produce an invalid fraction.

For 72/48, the input is:

72/48

The remainder sequence is 72 % 48 = 24 followed by 48 % 24 = 0, so the GCD is 24. The reduced fraction is 3/2. The numerator being larger than the denominator does not change how the GCD is computed.

For 37/73, the input is:

37/73

The remainder sequence eventually reaches 1, so the GCD is 1. Dividing by 1 leaves the original fraction unchanged. This is the correct behavior for an already simplified fraction.

For 1/2, the input is:

1/2

The first Euclidean step is 1 % 2 = 1, followed by 2 % 1 = 0. The GCD is 1, and the output is 1/2. This checks that the implementation does not assume that the numerator has a factor greater than 1.

For 100/80, the input is:

100/80

Euclid's algorithm gives gcd(100, 80) = 20. The algorithm divides both sides once by the complete GCD, producing 5/4. A repeated single-factor reduction would also work, but computing the GCD makes the operation independent of how many common factors the numbers contain.

For 99991/99989, the input is:

99991/99989

The two numbers are coprime, so their GCD is 1 and the output is unchanged. This case exercises the logarithmic algorithm on substantially larger values than the small examples while avoiding any dependence on the unspecified numerical upper bound of the easier version.

The official statement confirms the 1 second and 256 MB limits, the three samples, and the guarantee that the easier-version inputs are small enough for brute force.