【欧拉计划】12. Highly divisible triangular number

（本题取 $n$ 为第一个因数个数大于 $500$ 的三角形数 $76576500$）

【思路】依次枚举三角形数，每次 $\mathcal O(n)$ 求所有因数，因数个数大于 $500$ 就中断。时间复杂度为 $\mathcal O(n^2)$。

【优化】如果整数 $x$ 有因数 $i$，那么 $\dfrac{x}{i}$ 必然也是它的因数。因此可以把统计因数个数的时间复杂度降到 $\mathcal O(\sqrt n)$，总体优化到 $\mathcal O(n \sqrt n)$：

#include<stdio.h>
int fac(int x)
{
    if(x==1)return 1;
    int s=2;
    for(int i=2;i*i<=x;++i)
    {
        if(x%i==0)
        {
            ++s;
            if(i*i!=x)++s;
        }
    }
    return s;
}
int main()
{
    for(int i=1,x=1;;++i,x+=i)
    {
        if(fac(x)>500)
        {
            printf("%d",x);
            return 0;
        }
    }
    return 0;
}