HDU 2058 The sum problem——————数学

本是古典何须时尚 2022-05-10 15:08 110阅读 0赞

### The sum problem ###

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

--------------------

##### 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\]

--------------------

这道题的答案可以根据等差数列的性质得到：  
最大的区间长度 ：  
由 1 + 2 + 3 + ⋯ + 2 m > m \\large \\sqrt\{1+2+3+\\cdots+2m\}> m 1\+2\+3\+⋯\+2m>m  
 l m a x = 2 × m \\large l\_\{max\} =\\sqrt\{2\\times m\} lmax=2×m

由等差数列  
 S n = ( a 1 + a n ) × n 2 \\Large S\_n = \\frac\{(a\_1 + a\_n)\\times n\}\{2\} Sn=2(a1\+an)×n  
 S n = ( a 1 + a 1 + d ∗ ( n − 1 ) ) × n 2 \\Large S\_n = \\frac\{(a\_1 + a\_1+d\*(n-1))\\times n\}\{2\} Sn=2(a1\+a1\+d∗(n−1))×n  
 S n = ( 2 ∗ a 1 + d ∗ ( n − 1 ) ) × n 2 \\Large S\_n = \\frac\{(2\*a\_1+d\*(n-1))\\times n\}\{2\} Sn=2(2∗a1\+d∗(n−1))×n

又因为d=1，故：  
 S n = ( 2 ∗ a 1 + n − 1 ) × n 2 \\Large S\_n = \\frac\{(2\*a\_1+n-1)\\times n\}\{2\} Sn=2(2∗a1\+n−1)×n  
 a 1 = S n n − n − 1 2 \\Large a\_1 = \\frac\{S\_n\}\{n\}-\\frac\{n-1\}\{2\} a1=nSn−2n−1  
那么  
 a n = a 1 + n − 1 \\Large a\_n = a\_1 + n-1 an=a1\+n−1

对于这一道题：m就相当于Sn,  
假设 &ThickSpace; m = ( a i + a j ) × ( j − i + 1 ) 2 \\;\\Large m = \\frac\{(a\_i+a\_j)\\times (j-i+1)\}\{2\} m=2(ai\+aj)×(j−i\+1)  
我们可以枚举 a i a\_i ai  
因为我们知道最大的区间长度为 l m a x = 2 × m \\large l\_\{max\} =\\sqrt\{2\\times m\} lmax=2×m  
所以枚举 1 到 l 1到l 1到l的所有值  
那么根据上边的可以得到  
 a 1 = m l − l − 1 2 \\Large a\_1 = \\frac\{m\}\{l\}-\\frac\{l-1\}\{2\} a1=lm−2l−1  
 a n = a 1 + n − 1 \\Large a\_n = a\_1 + n-1 an=a1\+n−1  
只要 ( a 1 + a 2 ) ∗ l 2 = = m (a\_1+a\_2)\*\\frac\{l\}\{2\} == m (a1\+a2)∗2l==m  
就好了

代码很短，就这几行：

--------------------

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        
            int n,m;
            while(~scanf("%d %d",&n,&m)&&(n|m))
            {
        
                    int l=sqrt(2*m);//最大区间长度为 L
                    int a1,an;
                    for(int k=l;k>0;--k)//区间长度为k
                    {
        
                            a1 = m/k-(k-1)/2;
                            an = a1 + k-1;
                            if((a1 + an )*k/2 == m)
                                    printf("[%d,%d]\n",a1,an);
                    }
                    printf("\n");
            }
            return 0;
    }