依題目所述,我們可以把題目整理成
1 + 2 + … + n > 輸入值s
求出最小的n (第二個答案)
(1+2+…+n) - s (第一個答案)
我們可以列出不等式:
n(n+1)/2 > s (梯形公式)
整理一下
n(n+1) > 2s
n^2 + n > 2s
n^2 + n + (1/2)^2 > 2s + (1/2)^2 (配方法)
(n+(1/2))^2 > 2s + (1/4)
(n+(1/2))^2 > ((8s+1)/4)
n+(1/2) > sqrt(8s+1) / 2
n > (sqrt(8s+1) - 1) / 2
因為 n ∈ N //n是整數
如果這邊使用
n = ceil( (sqrt(8s+1) - 1) / 2 ) //無條件進位
會在 sqrt(8s+1) ∈ N 時,出現 n = (sqrt(8s+1) - 1) / 2 ,與原式不合 (會算出「少加第0頁」的答案)
所以我們使用無條件捨去再+1
得等式:
n = ((int) sqrt(8s-1) - 1) / 2;
最後再用 n(n+1) - s 就能得到「少加的頁數」了
題外話,由於java有很穩定的指派順序,所以java能把這題的所有運算縮排成一排:StreamTokenizer st = new StreamTokenizer(new java.io.BufferedReader(new java.io.InputStreamReader(System.in)));
for(int x; st.nextToken()!=-1; System.out.println(-(x=(int)st.nval)+((x=((int)Math.sqrt((x<<3)+1)-1>>1)+1)*(x+1)>>1)+" "+x));
也沒有一定要縮成這樣,就是一個我自己小小的嗜好而已 ~嘻
註: 不能貼完整的程式碼,所以上面的程式碼是針對eof結束,本題是輸入0結束,所以還要再改一下。
希望這篇解題報告能幫助到你^_^
更正
大字體等式的下一行
「少加的頁數」
是 n(n+1) / 2 - s