先附上程式碼：
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int n,half,sum;
int front,rear,times;
while(scanf("%d",&n)!=EOF)
{
for(times=0,half=(n/2)+1,sum=0,rear=0,front=1 ; sum<n ; sum+=(++rear))
;
while(front<half)
{
if(sum>n)
sum-=(front++);
else
{
if(sum==n)
printf("%d-%d\n",front,rear),times++;
sum+=(++rear);
}
}
if(!times)
printf("No Solution...\n");
}
return 0;
}
我覺得已經夠快了，
可是上傳第三個測資點卻還是TLE…（以下為檢測結果
Killed
各位已AC的大大能否告訴我哪裡還有可以加速的地方？
謝謝～～
各位已AC的大大能否告訴我哪裡還有可以加速的地方？
謝謝～～
敝人目前已AC，但跑出來的速度慢到不行…（與上面的程式碼雷同
AC (953ms, 248KB)
是否有其他種解法？？
如果可以的話請那些跑出來是兩位數ms的大大給一下提示，謝謝！
如果輸入 X 可表為以 a 為首的連續 n 個整數和，即 a + (a+1) + ... + (a+n-1)，則 X = n(2a+n-1)/2，即 2X = n(2a+n-1)。n 和 2a+n-1 都是整數，也是 2X 的因數。
因為 2a+n-1 > n，所以 n < sqrt(2X)。因為輸入頂多一億，陣列只要夠一萬組解即可。
我們讓 n 從 2 開始，往 sqrt(2X)跑：
n 要能整除 2X 才有可能是答案，然後 2X/n - n + 1 = 2a 中的 a 必須要是正整數。
因為 n 越來越大，所以 a 只會越來越小，解出 a <= 0 的時候就可以 break 了。
這樣解是最快的算法，只是給出答案的順序與題目相反，也就是 a 大的會先給。所以我打算宣告 int[20000] 把它存起來，一次存兩個整數：a 跟 a+n-1（首尾）。C 陣列不會記得自己的大小，所以要寫 count 以備將來找得到尾巴。只要注意 count 每次是加 2 應該還蠻簡單的。輸出的時候從尾巴讀回來。
如果輸入 X 可表為以 a 為首的連續 n 個整數和，即 a + (a+1) + ... + (a+n-1)，則 X = n(2a+n-1)/2，即 2X = n(2a+n-1)。n 和 2a+n-1 都是整數，也是 2X 的因數。
因為 2a+n-1 > n，所以 n < sqrt(2X)。因為輸入頂多一億，陣列只要夠一萬組解即可。
我們讓 n 從 2 開始，往 sqrt(2X)跑：
n 要能整除 2X 才有可能是答案，然後 2X/n - n + 1 = 2a 中的 a 必須要是正整數。
因為 n 越來越大，所以 a 只會越來越小，解出 a <= 0 的時候就可以 break 了。
這樣解是最快的算法，只是給出答案的順序與題目相反，也就是 a 大的會先給。所以我打算宣告 int[20000] 把它存起來，一次存兩個整數：a 跟 a+n-1（首尾）。C 陣列不會記得自己的大小，所以要寫 count 以備將來找得到尾巴。只要注意 count 每次是加 2 應該還蠻簡單的。輸出的時候從尾巴讀回來。