第22~26题题目

完善程序

（最大公约数之和）下列程序想要求解整数nn的所有约数两两之间最大公约数的和对 10007

求余后的值，试补全程序。举例来说，4 的所有约数是 1, 2, 4 。1 和 2 的最大公约数为 1

；2 和 4 的最大公约数为 2 ；1 和 4 的最大公约数为 1 。于是答案为1 + 2 + 1 = 4

要求getDivisor函数的复杂度为??(√??)，gcdgcd 函数的复杂度为??(log max(??, ??))。

#include <iostream>
using namespace std;
const int N = 110000, P = 10007;
int n;
int a[N], len;
int ans;
void getDivisor() {
	len = 0;
	for (int i = 1; ① <= n; ++i)
		if (n % i == 0) {
			a[++len] = i;
			if ( ② != i) a[++len] = n / i;
		}
}
int gcd(int a, int b) {
	if (b == 0) {
		③ ;
	}
	return gcd(b, ④ );
}
int main() {
	cin >> n;
	getDivisor();
	ans = 0;
	for (int i = 1; i <= len; ++i) {
		for (int j = i + 1; j <= len; ++j) {
			ans = ( ⑤ ) % P;
		}
	}
	cout << ans << endl;
	return 0;
}

①_____________________