大神的世界

題目概要:

給你一數n  (3 <= n <= 1000000)

請找出1~n之間，連續數字和為n的數列共有幾組

想法:

1.

若存在某數k可整除n

則以k為中心，左右放置

故，此數列項數必為奇數

2.

若存在某數k除n餘t

則此數列共需2t項 (以k為基準，左邊t-1個，右邊t個)

成立條件

1. k之左側至少有(商數-1)/2個空間

2. k之左側至少有t-1個空間

程式碼內

第一個for迴圈的i

代表的是 "數列個數"

第二個for迴圈的i

代表的是 "餘數"

此處為第二個迴圈簡單做個說明

將n平均分給2i個位置

並將剩餘的部分給最右邊的位置

因為其他位置都可以藉由左右平衡而得

ex: 右1 跟 左1 借 1

     右2 跟 左2 借 2 

(此處位置是以k為中心)

因此，只須考慮最後一位 (因為它對面沒有位置可借)

是故，若剩餘的部分恰好為餘數，則數列成立

#include <iostream>

using namespace std;

int main()
{
    int n, ans;

    while(cin >> n && n)
    {
        ans = 0;
        
        if(n>3)
            for(int i = 3; n/i > i/2 ; i+=2)
                if(n%i == 0)
                    ans++;

        for(int i = 1; n/(2*i) > i-1; i++)
            if(n%(2*i) == i)
                ans++;

        cout << ans << endl;
    }
    return 0;
}