下面 count_triple 函数（枚举本原勾股数）的时间复杂度为：
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); }
int count_triple(int n) {
int cnt = 0;
for (int v = 1; v * v * 4 <= n; v++)
for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)
if (gcd(u, v) == 1) {
int a = u*u - v*v, b = u*v*2, c = u*u + v*v;
cnt += n / (a + b + c);
}
return cnt;
}
- A. O(√n)
- B. O(n)
- C. O(n·log n)
- D. O(n·√n)
正确答案：C