下面 count_triple 函数的时间复杂度为（用欧几里得公式枚举勾股数）：
int gcd(int m,int n){ return m==0?n:gcd(n%m,m); }
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) { // Euclid 公式生成本原勾股数
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²log n)
- C. O(n log n)
- D. O(n)
正确答案：C