{"raw_statement":[{"iden":"statement","content":"Vasya is studying number theory. He has denoted a function _f_(_a_, _b_) such that:\n\n*   _f_(_a_, 0) = 0;\n*   _f_(_a_, _b_) = 1 + _f_(_a_, _b_ - _gcd_(_a_, _b_)), where _gcd_(_a_, _b_) is the greatest common divisor of _a_ and _b_.\n\nVasya has two numbers _x_ and _y_, and he wants to calculate _f_(_x_, _y_). He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly."},{"iden":"input","content":"The first line contains two integer numbers _x_ and _y_ (1 ≤ _x_, _y_ ≤ 1012)."},{"iden":"output","content":"Print _f_(_x_, _y_)."},{"iden":"examples","content":"Input\n\n3 5\n\nOutput\n\n3\n\nInput\n\n6 3\n\nOutput\n\n1"}],"translated_statement":[{"iden":"statement","content":"Vasya 正在学习数论。他定义了一个函数 #cf_span[f(a, b)]，满足：\n\nVasya 有两个数 #cf_span[x] 和 #cf_span[y]，他希望计算 #cf_span[f(x, y)]。他尝试自己计算，但发现按照他想要的方式计算这个函数可能需要非常长的时间。因此，他决定请你实现一个程序，以快速计算这个函数。\n\n第一行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ 1012]）。\n\n请输出 #cf_span[f(x, y)]。\n\n"},{"iden":"input","content":"第一行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ 1012]）。"},{"iden":"output","content":"请输出 #cf_span[f(x, y)]。"},{"iden":"examples","content":"输入\n3 5\n输出\n3\n\n输入\n6 3\n输出\n1"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ f : \\mathbb{Z}^+ \\times \\mathbb{Z}^+ \\to \\mathbb{Z}^+ $ be a function such that:  \n$$ f(x, y) = \\gcd(x, y) $$\n\n**Constraints**  \n1. $ x, y \\in \\mathbb{Z}^+ $  \n2. $ 1 \\le x, y \\le 10^{12} $\n\n**Objective**  \nCompute $ f(x, y) = \\gcd(x, y) $.","simple_statement":null,"has_page_source":false}