问题 C: 最大公约数之和

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:56 解决:17

题目描述

(最大公约数之和)下列程序想要求解整数 n的所有约数两两之间最大公约数的和对 10007 求余后的值,试补全程序。

举例来说,4的所有约数是 1, 2, 4。1 和 2 的最大公约数为 1;2 和 4 的最大公约数为 2;1 和 4 的最大公约数为 1 。于是答案为 1 + 2 + 1 = 4。

要求 getDivisor 函数的复杂度为 O(sqrt(n)),gcd 函数的复杂度为O(logmax(a,b))。

输入

一个数字n

输出

最大公约数之和

样例输入 复制

4

样例输出 复制

4

提示

2018年CSPJ-w1


完善题: 2727 2018J-完善1-最大公约数之和