120. What the Frac (Easier Version)

Codeforces

IDCF10269120

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Your 5-year-old cousin from the CodeRams Contest #5 (Problem 4) is now in 4th grade, and he is learning how to simplify fractions. Unfortunately, he doesn't really understand them, and he needs your help in simplifying fractions. For this problem, you must write a program to convert a fraction $a$/$b$ to simplest form. For example, if the fraction was $6$/$8$, you can factor out a $2$, and the fraction simplifies to $3$/$4$, which is in simplest form. The only line of input contains a single fraction $a$/$b$: the fraction you need simplify. $a$/$b$ can be greater than one, but $a$ will not be a multiple of $b$. So $3$/$2$ would be a valid input, but $6$/$2$ would not. Output a single fraction $c$/$d$ in the same format as the input: the input fraction, in simplest form, as described above. In this problem, the input will be small enough for a brute force solution that tries all factors to run efficiently. ## Input The only line of input contains a single fraction $a$/$b$: the fraction you need simplify. $a$/$b$ can be greater than one, but $a$ will not be a multiple of $b$. So $3$/$2$ would be a valid input, but $6$/$2$ would not. ## Output Output a single fraction $c$/$d$ in the same format as the input: the input fraction, in simplest form, as described above. [samples] ## Note In this problem, the input will be small enough for a brute force solution that tries all factors to run efficiently.

**Definitions** Let $ a, b \in \mathbb{Z}^+ $ be integers such that $ 1 \leq a, b \leq 100 $, $ a \not\equiv 0 \pmod{b} $, and the fraction is $ \frac{a}{b} $. **Constraints** 1. $ \gcd(a, b) > 1 $ (since the fraction is not already in simplest form) 2. $ a \not\equiv 0 \pmod{b} $ (i.e., the fraction is not an integer) **Objective** Find integers $ c, d \in \mathbb{Z}^+ $ such that: $$ \frac{c}{d} = \frac{a}{b} \quad \text{and} \quad \gcd(c, d) = 1 $$ Output $ \frac{c}{d} $, where $ c = \frac{a}{\gcd(a,b)} $, $ d = \frac{b}{\gcd(a,b)} $.

API Response (JSON)

{
  "problem": {
    "name": "120. What the Frac (Easier Version)",
    "description": {
      "content": "Your 5-year-old cousin from the CodeRams Contest #5 (Problem 4) is now in 4th grade, and he is learning how to simplify fractions. Unfortunately, he doesn't really understand them, and he needs your h",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269120"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Your 5-year-old cousin from the CodeRams Contest #5 (Problem 4) is now in 4th grade, and he is learning how to simplify fractions. Unfortunately, he doesn't really understand them, and he needs your h...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b \\in \\mathbb{Z}^+ $ be integers such that $ 1 \\leq a, b \\leq 100 $, $ a \\not\\equiv 0 \\pmod{b} $, and the fraction is $ \\frac{a}{b} $.\n\n**Constraints**  \n1. $ \\gcd(a, b) > 1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments