代码

#include <algorithm>

#define U unsigned int
#define UL unsigned long long
#define LOG2(x) ((U)(8 * sizeof (UL) - __builtin_clzll((x)) - 1))
UL fast_sqrt(UL n)
{
    if (n < 4) return (n == 0 ? 0 : 1);
    U nl = LOG2(n); nl -= nl & 1;
    static const U P[] = {8, 4, 11, 9, 14, 15, 14, 13, 19, 18, 14, 29};
    static const U Q[] = {8, 4, 9, 7, 10, 10, 9, 8, 11, 10, 7, 15};
    UL p = P[(n >> (nl - 2)) - 4], q = Q[(n >> (nl - 2)) - 4], t;
    if ((n >> (nl - 2)) - 4 == 1) if (n >> (nl - 3)) p = 10, q = 9; else p = 14, q = 12;
    t = (q * q * n >> nl) + p * p; q *= 2 * p;
    if (t * t << nl >= n * q * q) t --;
    p = (q * q * n >> nl) + t * t; q *= 2 * t;
    UL l = (p << (nl >> 1)) / q + 1;
    if (l * l > n) l --;
    if (l * l > n) l --;
    return l;
}

void sort(unsigned *a, int n) {
	for (int i = 0; i < n; ++ i) a[i] = fast_sqrt(a[i]);

}

评测结果