举例来说,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.
