A61443. （最大公约数之和）下列程序想要求解整数：举例来说，4的所有约数是1,2,4。1和2的最大公约数为1；2和4的最大公约数为2；1和4的最大公约数为1。于是答案为1 + 2 + 1 = 4。要求 getDivisor 函数的复杂度为0(√n)，gcd 函数的复杂度为O(log max(a, b))。#include<iostream>
填空题
知识点
题目描述
（最大公约数之和）下列程序想要求解整数：
举例来说，4的所有约数是1,2,4。1和2的最大公约数为1；2和4的最大公约数为2；1和4的最大公约数为1。于是答案为1 + 2 + 1 = 4。要求 getDivisor 函数的复杂度为0(√n)，gcd 函数的复杂度为O(log max(a, b))。
#include<iostream>
using namespace std;
const int N =110000, P = 10007;
int n;
int a[N], len;
int ans;
//计算出所有公约数，并存储在a数组中
void getDivisor(){
len = 0;
for(int i=1;__(1)___<=n;++i)
if (n % i == 0) {
a[++len] = i;
if( __(2)__!=i)a[++len]=n/i;
}
}
//求两个数的最大公约数
int gcd(int a,int b) {
if (b == 0) {
return ___(3)___ ;
}
return gcd(b, ___(4)____ );
}
int main() {
cin >> n;
getDivisor();
ans = 0;
for (int i = 1; i <= len; ++i) {
for (int j = i + 1; j <= len; ++j) {
ans=( ___(5)___ )%P;
}
}
cout << ans << endl;
return 0;
}