1006-小明的烦恼_南理ACM集训队2021级考核题目合集

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小明在你的帮助下成功选出了幸运数字，这个数字不仅给TA带来桃花运，还成功地加入了学校的ACM集训队。

现在小明每天都要参加学校的集训，晚上不能一直陪着小王聊天了。不过为了防止小明去和集训队里的别人聊天从而影响学习浪费时间，所以小王给小明布置了一个任务：

定义： $F_1 = A, F_2 = B, F_n = F_{n - 1} + F_{n-2}(n > 2)$ ，求 $\gcd(F_N, F_{N+1})$ 。

小明刚开始学习ACM，技术还很菜，这个题明显有点难到TA了，但因为对小王的爱意，TA勤勤恳恳地把每一项答案都算出来了。

现在小明也把A、B、N都写给你，想让你也尝试计算一下。

仅一行，三个正整数A、B、N。

仅一行一个正整数表示答案。

示例1

复制

2 4 5

复制

F的序列为：2 4 6 10 16 26 ......
第5项16和第6项26的最大公因（约）数为2

，你可以理解为N的长度不超过
另外，表示取a和b的最大公因（约）数