HDOJ 2058 The sum problem

这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

这题说难也难，说不难也不难，就是特别容易超时。

题目地址：

http://acm.hdu.edu.cn/showproblem.php?pid=2058

思路：

暴力肯定不行，这题要结合数学公式，多项式的和，但是必须的从序列长度d如何，若从起始值入手，一样会TLE。其次要注意：题目有这么一句话： print a blank line after each test case. 结果我考虑复杂了，以为最后一组数据不能有空行，搞的一直PE。 [s:3] 先给出一个纯暴力的TLE的代码：

 // Author: Tanky Woo
// HDOJ 2058

#include 
#include 
#include 
using namespace std;
int sum;
int N, M;
int main()
{
    while(scanf("%d %d", &N;, &M;) && (M||N))
    {
        for(int i=1; i<=M && i<=N; ++i)
        {
            sum = 0;
            for(int j=i; j<=M && i<=N; ++j)
            {
                if(sum M)
                    break;
            }
        }
        printf("\n");
    }
    return 0;
}

下面这个虽然优化了，但是仍然TLE

 #include 
#include 
#include 
using namespace std;
int sum;
int N, M;
int main()
{
    int flag = 0;
    while(scanf("%d %d", &N;, &M;) && (M||N))
    {
        if(flag)
            printf("\n");
        flag = 1;
        for(int i=0; i<=M; ++i)
        {
            // 起始a+1..a+d
            double temp = sqrt(double((2*i+1)*(2*i+1)+8*M))/2.0 - 0.5;
            if(fabs(temp-(int)temp) < 1e-6)
            {
                printf("[%d,%d]\n", i+1,(int)temp);
            }
        }
    }
    return 0;
}

上面这个方法，结合了数学公式。但是仍然超时，这是因为N和M都太大了。观察a+1,a+2...a+d 全部相加等于M 即(a+1+a+d)*d/2 = M 这里d是平方，我们可以从长度d入手，这样就能把范围由M转换成M^1/2 [s:20]

 // Accepted 2058 15MS 212K 426 B C++ Tanky Woo 
#include 
#include 
#include 
using namespace std;
int N, M;
int main()
{
    int flag = 0;
    while(scanf("%d %d", &N;, &M;) && (M||N))
    {
        int i;
        int len = int(sqrt(M*2.0));  // ①
        for(i=len; i>=1; --i)
        {
            int temp = M-(i*i+i)/2;   // ②
            if(temp%i == 0)
                printf("[%d,%d]\n", temp/i+1, temp/i+i);
        }
        printf("\n");
    }
    return 0;
}

这里把①和②解释下： ①：当a+1,a+2...a+3相加等于M时，即 (a+1+a+d)d/2 = M 而a最小是0，所以(d+1)d/2=M时d去最大值，就是这步把时间复杂度减小的。 d就是sqrt(2*M)

②：(a+1+a+d)d/2 = M 所以ad + (d+1)*d/2 = M(先前漏掉了d。经syx兄提醒，已改正) 所以要使等式成立，M-(d+1)/2必须是d的倍数。