举例来说,4的所有约数是1,2,4。1和2的最大公约数为1;2和4的最大公约数为2;1和4的最大公约数为1。于是答案为1 + 2 + 1 = 4。
要求getDivisor 函数的复杂度为𝑂(),gcd 函数的复杂度为𝑂(log max(𝑎, 𝑏))。
#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; }