I'm bored with life

Codeforces

Easy

Math

Number Theory

I'm bored with life

Given two positive integers, find the maximum value of gcd(a, b) over all pairs formed by choosing one divisor of each number.

Acceptance 0%

Start Practice

Problem Statement

You are given two positive integers $a$ and $b$ .

Consider all possible pairs $(x, y)$ such that:

$x$ is a positive divisor of $a$ ,
$y$ is a positive divisor of $b$ .

For every such pair, compute $\gcd(x, y)$ . Your task is to output the maximum value that can be obtained.

Intuition

The answer depends only on the greatest common divisor of the two numbers, because any common divisor of $a$ and $b$ can be chosen as a divisor of each.

Input Format

The input consists of a single line containing two integers $a$ and $b$ .

Output Format

Print one integer — the maximum possible value of $\gcd(x, y)$ over all valid divisor pairs.

Constraints

$1 \le a, b \le 10^9$
$a$ and $b$ are positive integers

Examples

Sample cases returned by the problem API.

Example 1

Input

10 12

Output

Explanation

Divisors of 10 are 1, 2, 5, 10 and divisors of 12 are 1, 2, 3, 4, 6, 12. The largest gcd obtainable is 2, for example with x = 2 and y = 2.

Example 2

Input

18 24

Output

Explanation

A common divisor of both numbers cannot exceed gcd(18, 24) = 6, and this value is achievable by choosing x = 6 and y = 6.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress