题目描述

给定两个正整数，求它们的最大公约数。

它的递归函数如下：

设 $f(x,y)$ 为计算 $x,y$ 最大公约数的函数。

$$f(x,y)=\begin{cases} x\ \ \ \ if (y=0)\\ f(y,x\% y)\ \ \ \ if(y>0) \end{cases} $$

输入格式

输入一行，包含两个正整数 $x,y,1\leq x,y\leq 10^9$。

输出格式

输出一个正整数，即这两个正整数的最大公约数。

6 9

3