日行一算（Consecutive Integer-連續整數）

• 2022 年 2 月 22 日
• 筆記
• 技術貼, 演算法OJ

題目

題目描述
2005年的百度之星初賽有這麼一道題，一個正整數有可能可以被表示為 m(m>1) 個連續正整數之和，如：

15=1+2+3+4+5
15=4+5+6
15=7+8

但現在你的任務是判斷給定的整數n能否表示成連續的m(m>1)個正整數之和。

解答要求
時間限制：1000ms, 記憶體限制：100MB
輸入
輸入只有一個整數n (1<n<230 +1)。

輸出
若n能表示成連續的m(m>1)個正整數之和則輸出「YES」，否則輸出「NO」。

解題思路

分析：Java遞歸

1. 初看這道題時，只覺得不需思考，循環就可以解決
   思路：嵌套循環，逐項相加，當前n項和大於目標值，則減去左側小的值使和小於目標值，再繼續如此，直到等於目標值或循環結束。
   最終在百萬級別超時。
2. 此時意識到雙重循環耗時嚴重，需分析演算法再進行求解
   思路：連續數相當於等差數列，差為1，利用前n項和公式，使其等於目標值，根據項數不同，只要能求出首項為整數即可。
   最終在十億級別超時。
3. 終於，這個數量級已經不是循環能搞定的了，必須在數學層面想點別的招了
   思路：
   奇數，一個奇數n可表示為（n+1）/2，（n-1）/2.所以奇數必然可以寫成連續數。奇數的倍數是只需要在原有奇數序列兩端不停的+1-1即可，直到左側最小數變成0，此時為（n-n）/2，同時可以發現最大數為n，此時連續個數=奇數值，以後無論多少倍，在基礎上加相應倍數即可。（例7：3，4 翻倍14：2，3，4，5 再翻28：0，1，2，3，4，5，6，7 此時除去0，個數與奇數值相同，無論在以後怎麼加都ok）
   那就簡單了，目標數字能夠除以2，最終是奇數即可（除了1），你想想是不是只有2的n次方不滿足條件。
   所以這道題的意義就是判斷輸入是否為2的n次方。

public class Main {
    public static void main(String[] args) {      
        System.out.println(method(new Scanner(System.in).nextInt()));
    }
    
    private static String method(int num){
        if(num == 1){
            return "NO";
        }
        if(num %2 !=0 ){
            return "YES";
        }
        return method(num/2);
    }
}