題目鏈接：http://poj.org/problem?id=2853

題意：某些正整數可由幾個連續數相加而成，且方法可能有多種，如3 = 1 + 2， 9 = 4 + 5 = 2 + 3 + 4?

給出任意小于2^31的正整數，問有多少種方法。

?

?思路：其實就是關于公差為1的等差數列的問題。

由 num = (a1 + an) * n / 2?， an = a1 + n - 1可以得到

令 k = 2 * num / n

則a1 = (k - n + 1) / 2， an = (k + n - 1)?

?

所以枚舉sqrt(2 * num) 的所有因子，每一組因子中小的為n，大的為k

求出對應的a1，an，若滿足大于0，小于num，是整數這些條件，ans++

?1?#include?<iostream>
?2?#include?<cstring>
?3?using?namespace?std;
?4?
?5?//const?int?M?=?100000;
?6?const?int?N?=?200000;
?7?//int?pr[M],?pri;
?8?/*
?9?void?prime()
10?{
11?????pr[0]?=?2;?pr[1]?=?3;?pr[2]?=?5;?pr[3]?=?7;
12?????pri?=?4;
13?????for(int?i=11;?i<=N;?i++)
14?????{
15?????????int?flag?=?0;
16?????????for(int?i=0;?i<pri;?i++)
17?????????{
18?????????????if(i%pr[pri]==0)
19?????????????{
20?????????????????flag?=?1;
21?????????????????break;
22?????????????}
23?????????}
24?????????if(flag?==?0)
25?????????????pr[pri++]?=?i;
26?????}
27?}
28?*/
29?int?main()
30?{
31?????int?n,?no;
32?????long?long?num;
33?????//prime();
34?????cin?>>?n;
35?????for(int?i=1;?i<=n;?i++)
36?????{
37?????????cin?>>?no?>>?num;
38?????????if(num==0?||?num==1?||?num==2)
39?????????????cout?<<?no?<<?"?0"?<<?endl;
40?????????else
41?????????{
42?????????????int?ans?=?0;
43?????????????num?*=?2;
44?????????????for(int?j=2;?j*j<=num;?j++)
45?????????????{
46?????????????????if(num%j==0)
47?????????????????{
48?????????????????????long?long?k?=?num?/?j;
49?????????????????????long?long?a1?=?(k?+?1?-?j)?/?2,?an?=?(k?+?j?-?1)?/?2;
50?????????????????????if(a1>0?&&?an?<num?&&?a1*2?==?(k+1-j)?&&?an*2==(k+j-1))
51?????????????????????????ans++;
52?????????????????????//cout?<<?j?<<?"????????"?<<?a1?<<?"?????"?<<?an?<<?endl;
53?????????????????}
54?????????????}
55?????????????cout?<<?no?<<?"?"?<<?ans?<<?endl;
56?????????}
57?????}
58?
59?????return?0;
60?}View Code?

?

?------------------------

這題浪費了很多時間，還是用筆演算清楚才去敲比較好。。。

轉載于:https://www.cnblogs.com/byluoluo/p/3454048.html

總結

以上是生活随笔為你收集整理的POJ 2853 Sequence Sum Possibilities的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。