ACM – UVa138 – 数学基础

点击量:27

这道题目其实就是推个公式,主要还是考验编程技巧。。
首先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 = 0;
        // 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");

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注