Call Stack

题目背景

在 C 语言中, 函数是一组完成特定任务的语句集合. 每个程序至少包含一个 main() 主函数, 同时可以根据需要定义多个自定义函数, 以实现代码的模块化和复用. 那么, 操作系统具体是如何实现函数（递归）调用的? 如何记录调用与被调用函数（递归）实例之间的关系? 如何实现函数（递归）调用的返回? 又是如何维护同时活跃的所有函数（递归）实例的? 所有这些问题的答案, 都可归结于栈.

在Windows等大部分操作系统中, 每个运行中的二进制程序都配有一个调用栈（call stack）或执行栈（execution stack）. 借助调用栈可以跟踪属于同一程序的所有函数, 记录它们之间的相互调用关系, 并保证在每一调用实例执行完毕之后, 可以准确地返回.

如图4.3所示, 调用栈的基本单位是帧（frame）. 每次函数调用时, 都会相应地创建一帧, 记录该函数实例在二进制程序中的返回地址（return address）, 以及局部变量、传入参数等, 并将该帧压入调用栈. 若在该函数返回之前又发生新的调用, 则同样地要将与新函数对应的一帧压入栈中, 成为新的栈顶. 函数一旦运行完毕, 对应的帧随即弹出, 运行控制权将被交还给该函数的上层调用函数, 并按照该帧中记录的返回地址确定在二进制程序中继续执行的位置. 在任一时刻, 调用栈中的各帧, 依次对应于那些尚未返回的调用实例, 亦即当时的活跃函数实例（active function instance）. 特别地, 位于栈底的那帧必然对应于入口主函数 main(), 若它从调用栈中弹出, 则意味着整个程序的运行结束, 此后控制权将交还给操作系统.

题目描述

定义函数 $f(m, n)$ 满足 $$ f(m, n) = \begin{cases} n &, m = 0 \\ g(m - 1, m + n) + \gcd (m, n) &,m > 0 \end{cases} $$

函数 $g(m, n)$ 满足

$$ g(m, n) = \begin{cases} n &, m = 0 \\ f(m - 1, n + 1) + \gcd (m, n) &,m > 0 \end{cases} $$

其中 $\gcd (m, n)$ 表示 $m$ 与 $n$ 的最大公约数, 通常使用辗转相除法递归求得, 计算方法为 $$ \gcd (m, n) = \begin{cases} m &, n = 0 \\ \gcd (n, m ~ \text{mod} ~ n) &, n \neq 0 \end{cases} $$

其中 $\text{mod}$ 为取模运算.

输入两个整数 m n, 请通过手写调用栈模拟函数调用求出 $f(m, n)$.

注意：本题的系统堆栈空间只有 4MB, 这意味着数据规模较大时直接通过递归求解 $f(m, n)$ 将导致栈溢出.

输入格式

输入共 1 行, 包含 2 个整数 m n.

输出格式

输出共 1 行, 为 $f(m, n)$.

样例

样例输入

4 2

样例输出

17

样例解释

$f(4, 2) = g(3, 6) + \text{gcd}(4, 2) = g(3, 6) + 2$.

$g(3, 6) = f(2, 7) + \text{gcd(3, 6)} = f(2, 7) + 3$.

$f(2, 7) = g(1, 9) + \text{gcd}(2, 7) = g(1, 9) + 1$.

$g(1, 9) = f(0, 10) + \text{gcd}(1, 9) = 10 + 1 = 11$.

故 $f(4, 2) = 17$.

说明

对于 $20\%$ 的数据, 满足 $0 \leq m \leq 10^4$, $0 \leq n \leq 10^6$.

对于 $100\%$ 的数据, 满足 $0 \leq m \leq 10^6$, $0 \leq n \leq 10^6$.

计算结果可能超出 int 所能表示的数据范围, 但不会超过 long long 类型所能表示的数据范围.