不是VIP会员,不能显示答案

题目解答

题目:
(最大公约数之和)下列程序想要求解整数 n 的所有约数两两之间最大公约数的和对10007求余后的值,试补全程序。(第一空2 分,其余 3 分)
举例来说,4的所有约数是1,2,4。1和2的最大公约数为1;2和4的最大公约数为2;1和4的最大公约数为1。于是答案为1 + 2 + 1 = 4。

要求getDivisor 函数的复杂度为O(√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;
void getDivisor() {
	len = 0;
	for (int i = 1; i*i <= n; ++i)
		if (n % i == 0) {
			a[++len] = i;
			if ( n/i != i) a[++len] = n / i;
		}
}
int gcd(int a, int b) {
	if (b == 0) {
		return a ;
	}
	return gcd(b, a%b );
}
int main() {
	cin >> n;
	getDivisor();
	ans = 0;
	for (int i = 1; i <= len; ++i) {
		for (int j = i + 1; j <= len; ++j) {
			ans = ( ans+gcd(a[i],a[j]) ) % P;
		}
	}
	cout << ans << endl;
	return 0;
}
考点: 0
分析:
解答: (1).解析:其实就是枚举到sqrt(n)

(2). 解析:防止重复约数

(3). 解析:gcd模板还不会

(4). 解析:同上

(5).根据题目描述枚举约数
评论:
老师: 0