NOIP2018 完善程序
1.（最大公约数之和）下列程序想要求解整数n的所有约数两两之间最大公约
数的和对10007求余后的值，试补全程序。（第一空 2 分，其余 3 分）
举例来说，4的所有约数是1,2,4。1和2的最大公约数为1；2和4的最大公约 数为2；1和4的最大公约数为1。于是答案为1 + 2 + 1 = 4。
要求 getDivisor 函数的复杂度为O函数的复杂度为O(log max(a,b))。
#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; (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) {
(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;
}
阅读代码，填空
1
2
3
4
5
发表评论