###### tags: `APCS`
# **a471－givesum~連續整數的固定和**
### **題目連結：** [**a471**](https://zerojudge.tw/ShowProblem?problemid=a471)
### **題目解析**
目要求找出一個整數 n 的所有連續整數和的區間，並輸出這些區間。如果沒有符合的區間，則輸出 "No Solution..."。
### **解題方向-1**
* 逐一檢查所有可能的連續整數起點 i。
* 從起點 i 開始累加整數，直到和等於或超過 n。
* 如果找到和等於 n 的連續整數區間，則輸出該區間。
* 如果找遍所有可能區間後，沒有找到符合的，則輸出 "No Solution..."。
### **程式解析-1**
* 使用 while True 不斷讀取輸入直到結束。
* 內部使用兩層 for 迴圈來檢查每個可能的連續整數區間。
* 當找到一個符合的區間時，設置 noSolution 為 False 並輸出區間。
* 若所有區間都檢查完仍未找到符合的，則輸出 "No Solution..."。
* 每個答案之間用一個空行隔開。
### **完整程式碼-1**

while True:
    try:
        N = int(input())
        noSolution = True

        for i in range(1, N):
            sum = 0
            for j in range(i, N):
                sum += j
                if sum == N:
                    print(f"{i}-{j}")
                    noSolution = False
                    break

        if noSolution:
            print("No Solution...")

        print()
    except EOFError:
        break

### **解題方向-2**
* 以數學方式找出連續整數區間的總和。
* 將總和公式 (a + (a+1) + ... + (a+k-1)) 化簡為 k*a + k*(k-1)/2 = N。
* 將公式轉換為 (2*N)/k = 2a + k - 1。
* 檢查 (2*N)/k 是否為整數且 (2a + k - 1) 是否為偶數。
* 如果上述條件成立，則可找到一個符合條件的區間。
### **程式解析-2**
* 使用 while True 不斷讀取輸入直到結束。
* 使用數學方法來找出所有可能的連續整數區間。
* 使用一個清單 output 來存儲所有符合條件的區間。
* 檢查 (2*N)/k 是否為整數且 (2*N/k - k + 1) 是否為偶數，若是則計算區間起點和終點。
* 若沒有找到任何區間，輸出 "No Solution..."。
* 若找到符合的區間，逆序輸出這些區間。
* 每個答案之間用一個空行隔開。
### **完整程式碼-2**

import math

# start
while True:
    try:
        N = int(input())

        noSolution = True

        output = []

        for i in range(2, int(math.sqrt(2 * N)) + 1):
            if (2 * N) % i == 0:
                if (int(2 * N / i) - i + 1) % 2 == 0:
                    a = (int(2 * N / i) - i + 1) / 2
                    noSolution = False

                    if a <= 0:
                        break
                    else:
                        end = a + i - 1
                        tmp = f"{int(a)}-{int(end)}"
                        output.append(tmp)

        if noSolution:
            print("No Solution...")
        else:
            for i in range(len(output) - 1, -1, -1):
                print(output[i])
        print()
    except:
        break

### **版本二補充說明**
* noSolution = True：初始化標誌變數 noSolution 為 True，用於檢查是否有找到符合條件的區間。
* output = []：初始化空列表 output 用於存儲所有找到的區間。
* for i in range(2, int(math.sqrt(2 * N)) + 1):：遍歷可能的區間長度 i，範圍從 2 到 sqrt(2 * N)。
* 這裡使用 sqrt(2 * N) 是因為當 i 增加時，區間的和會增加，而 sqrt(2 * N) 是合理的最大範圍。
* if (2 * N) % i == 0:：檢查 (2 * N) / i 是否為整數，若是，則 i 是可能的區間長度。
* if (int(2 * N / i) - i + 1) % 2 == 0:：檢查 (2a + k - 1) 是否為偶數，若是，則 a 是可能的起點。
* a = (int(2 * N / i) - i + 1) / 2：計算起點 a。
* noSolution = False：設置標誌變數 noSolution 為 False，表示找到了符合條件的區間。
* if a <= 0:：若起點 a 小於等於 0，則跳出循環。
* else:：否則，計算區間終點並將區間加到 output 清單中。
* end = a + i - 1：計算終點。
* tmp = f"{int(a)}-{int(end)}"：格式化區間為字串。
* output.append(tmp)：將區間字串加入 output 清單。
* if noSolution:：若未找到任何符合條件的區間，輸出 "No Solution..."。
* else:：否則，逆序輸出所有找到的區間。
* for i in range(len(output) - 1, -1, -1):：逆序遍歷 output 清單。
* print(output[i])：輸出每個區間。
* print()：在每個輸出後添加一個空行。

### 版本二數學推導
我們假設有一個連續整數區間，它的起點是 a，長度是 k，則這個區間的總和 S 可以表示為：
這個公式可以化簡為：
由於我們的目標和為 N，所以：
將公式兩邊乘以2來消除分數部分：
接下來，我們要找出這個公式中符合條件的 k 和 a。

#### 來看看 N = 27 的情況：
我們可以發現，當 (2 * N) / k 為整數且 (2a + k - 1) 為偶數時，我們可以計算出 a 和 k，並找出符合條件的區間。這些區間的總和都為 N。