The sum problem

Problem Description

Given a sequence 1,2,3,......N, your job is to calculate all the possible sub-sequences that the sum of the sub-sequence is M.

Input

Input contains multiple test cases. each case contains two integers N, M( 1 <= N, M <= 1000000000).input ends with N = M = 0.

Output

For each test case, print all the possible sub-sequence that its sum is M.The format is show in the sample below.print a blank line after each test case.

Sample Input

20 10
50 30
0 0

Sample Output

[1,4]
[10,10]

[4,8]
[6,9]
[9,11]
[30,30]

Sample Input

本来想前缀和搞搞的，一看1 <= N, M <= 1000000000，看来是公式题，给出一个M，不可能从1枚举到1000000000，所以要找一个枚举范围，等差数列求和公式：sum=n*a1+n*(n-1)/2,n要最大,就要a1=1,所以sum=n*(n+1)/2,变一下n<sqrt(2*sum),所以取n=sqrt(2*sum),接下来n从大到小枚举,用公式变形:a1=sum/n-(n-1)/2求出a1,求和如果等于M,输出[a1,a1+n-1].

#include <cstdio>

#include <iostream>

#include <string>

#include <sstream>

#include <cstring>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#include <map>

#define PI acos(-1.0)

#define ms(a) memset(a,0,sizeof(a))

#define msp memset(mp,0,sizeof(mp))

#define msv memset(vis,0,sizeof(vis))

using namespace std;

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt", "r", stdin);

    //freopen("out.txt","w",stdout);

#endif // LOCAL

    ios::sync_with_stdio(false);

    int n,m;

    while(cin>>n>>m,n||m)

    {

        int t=sqrt(*m);

        while(t)

        {

            int ans=m/t-(t-)/;

            if(ans*t+(t*(t-)/)==m)

                printf("[%d,%d]\n",ans,ans+t-);

            t--;

        }

        printf("\n");

    }

    return ;

}

巴特西

HDU 2058 The sum problem(枚举)

The sum problem

最新文章

热门文章