最近在做一道需要用到 gcd 的题,正当我急于回忆 gcd 怎么写时,忽然听说有个叫__gcd()的内置函数。

知乎 上说这是个built-in函数(也许可以简单地理解为内置函数)。

但我对它的时间复杂度一直很担忧,想看看它到底是怎么实现的,便在C++内置库bits/stl_algo.h的 1512 - 1527 行找到可能的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 /**
* This is a helper function for the rotate algorithm specialized on RAIs.
* It returns the greatest common divisor of two integer values.
*/
template<typename _EuclideanRingElement>
_EuclideanRingElement
__gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
{
while (__n != 0)
{
_EuclideanRingElement __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}

bits/stl_algo.h是C++的一个内置库,你引用algorithm库时就会引入这个库

欧拉筛求质数

欧拉筛是一种优秀的筛质数方法。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×