首页 > 试题广场 >

(最大公约数之和)下列程序想要求解整数𝑛的所有约数两两之间

[填空题]
(最大公约数之和)下列程序想要求解整数𝑛的所有约数两两之间最大公约数的和对10007求余后的值,试补全程序。(第一空2 分,其余 3 分)
举例来说,4的所有约数是1,2,4。1和2的最大公约数为1;2和4的最大公约数为2;1和4的最大公约数为1。于是答案为1 + 2 + 1 = 4。
要求getDivisor 函数的复杂度为O(),gcd 函数的复杂度为O(log max(𝑎, 𝑏))。

const
  P : longint = 10007;
var
  n, len, ans, i, j : longint;
  a : array[0..110000] of longint;
procedure getDivisor( );
var
  i : longint;
begin
  len := 0;
  i := 1;
  while     1 <= n do
  begin
    if n mod i = 0 then
    begin
      len := len + 1;
      a[len] := i;
      if     2 <> i then
      begin
        len := len + 1;
        a[len] := n div i;
      end;
    end;
    inc(i);
  end;
end;
function gcd(a, b : longint) : longint;
begin
  if b = 0 then
    3;
  exit( gcd(b, 4) );
end;
begin
  read(n);
  getDivisor( );
  ans := 0;
  for i := 1 to len do
    for j := i + 1 to len do
      ans := (5) mod P;
  writeln(ans);
end.



这道题你会答吗?花几分钟告诉大家答案吧!