ACM – UVa138 – 数学基础 -

这道题目其实就是推个公式，主要还是考验编程技巧。。

首先double的精度范围是15-16位，浮点数运算还是最快的，依据最后一个答案（总共10组），平方为16位刚好够用。

如果想要最精确的结果，当然还是使用long double或者long long来来保证精度问题。不过计算速度就会有所损失，采取二分的方法加速比较好。

利用double的代码：

    const double eps = 1e-10;
    for(double i = 8; i < maxn;i ++)
    {
        double res = i*(i+1)/2;
        ll ans = sqrt(res);
        if(res - ans*ans < eps)
            printf("%10lld %10lf\n", ans, i);
    }
    printf("done");

利用long long的代码:

    for(ull i = 8; i < maxn;i ++)
    {
        ull res = i*(i+1)/2;
        ull l = i/2, r = i;
        ull mid, ans;
        bool find = ;
        // bsearch
        while(l <= r)
        {
            mid = (l+r)/2;
            ans = mid * mid;
            if(ans == res)
            {
                find = 1;
                break;
            }
            else if(ans > res)
                r = mid - 1;
            else
                l = mid + 1;
        }
        if(find)
            printf("%10lld %10lld\n", mid, i);
    }
    printf("done");

不过有一点就是无论怎么个快法，不使用打表肯定是会超时的，所以算出来直接上交即可。= =。这在大赛中应该也是允许的吧。