hdu2058The sum problem解题报告---等差数列的和（数论）

                                        the sum problem

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 32097    Accepted Submission(s): 9580

 

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]

等差数列取多少项之和：

最大长度v = （int）sqrt(m)

AC Code:

#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<list>
#define mod 998244353
#define INF 0x3f3f3f3f
#define Min 0xc0c0c0c0
#define mst(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const double pi = acos(-1);
int n, m, v;
int main(){
    while(scanf("%d%d", &n, &m) != EOF){
        if(n == 0 && m == 0) break;
        v = (int)sqrt(2 * m);
        while(v){
            int res = m - v * (v - 1) / 2;
            if(res % v == 0){
                printf("[%d,%d]\n", res / v, res / v + v - 1);
            }
            v--;
        }
        printf("\n");
    }
    return 0;
}

暴搜...思路还是没有错的，TLE（数据很大）

TLE Code:

#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<list>
#define mod 998244353
#define INF 0x3f3f3f3f
#define Min 0xc0c0c0c0
#define mst(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const double pi = acos(-1);
int n, m, v;
void dfs(int s, int sum, int e){
    if(sum > m) return;
    if(sum == m){
        printf("[%d,%d]\n", s, e);
        return ;
    }
    for(int i = e + 1; i <= v; i++){
        if(sum + i > m) return;
        dfs(s, sum + i, i);
        return ;
    }
}
int main(){
    while(scanf("%d%d", &n, &m) != EOF){
        if(n == 0 && m == 0) break;
        v = min(m, n);
        if(m == 1){
            printf("[%d,%d]", 1, 1);
            continue;
        }
        for(int i = 1; i <= v; i++){
            dfs(i, i, i);
        }
        printf("\n");
    }
    return 0;
}