數字詩意

在詩人的眼中，數字是生活的韻律，也是詩意的表達。

小藍，當代頂級詩人與數學家，被賦予了”數學詩人”的美譽。他擅長將冰冷的數字與抽象的詩意相融合，并用優雅的文字將數學之美展現于紙上。

某日，小藍靜坐書桌前，目光所及，展現著 n 個數字，它們依次為 a1,a2,…,an，熠熠生輝。

小藍悟到，如果一個數能夠以若干個（至少兩個）連續的正整數相加表示，那么它就蘊含詩意。

例如，數字 6 就蘊含詩意，因為它可以表示為 1+2+3。

而 8 則缺乏詩意，因為它無法用連續的正整數相加表示。

小藍希望他面前的所有數字都蘊含詩意，為此，他決定從這 n 個數字中刪除一部分。

請問，小藍需要刪除多少個數字，才能使剩下的數字全部蘊含詩意？

輸入格式

第一行包含一個整數 n，表示展示的數字個數。

第二行包含 n 個整數 a1,a2,…,an，表示展示的數字。

輸出格式

輸出一個整數，表示小藍需要刪除的數字個數，以使剩下的數字全部蘊含詩意。

數據范圍

對于 30% 的評測用例，1≤n≤$10^3$，1≤ai≤$10^3$。
對于所有評測用例，1≤n≤2×$10^5$，1≤ai≤$10^{16}$。

輸入樣例：

3
3 6 8

輸出樣例：

1

樣例解釋

在樣例中，數字 3 可以表示為 1+2，數字 6 可以表示為 1+2+3，數字 8 無法表示為連續的正整數相加，因此，需要刪除的數字個數為 1。

【思路分析】

看到這一題我的第一直覺就是用二進制每一位的權值不能表示成連續的正整數相加

于是打表玩了一把

$2^0$ = 1 （x）

$2^1$ = 2 （x）

3 = 1 + 2 （√）

$2^2$ = 4 （x）

5 = 2 + 3 （√）

6 = 1 + 2 + 3 （√）

7 = 3 + 4（√）

$2^3$ = 8 （x）

…

貌似還真的是這樣，那么也就是說只有包含奇數因子的數才可以分成連續的正整數相加

我們證明一下

設數N不含有奇數質因子，那么N可以表示為 N = $2^k$，其中k為正整數。

假設N可以分解為m個連續正整數的和，設這m個連續正整數中最小的數為n，則這m個連續正整數的和為：
$$S=n+(n+1)+(n+2)+...+(n+m?1)$$

等差數列求和
$$S=\frac{m(2n+m?1)}{2}$$
如果m是奇數，那么 2n+m - 1是偶數 $S=\frac{m(2n+m?1)}{2}$中，m為奇數因子，這與N不含有奇數質因子矛盾。

如果m是偶數，設 m = 2p（p為正整數），則 S = p(2n + 2p + 1)

因為2n + 2p + 1為奇數，若S = N = $2^k$ （不含奇數因子的數），此時 2n + 2p + 1 為其中一個奇數因子，這與N不含有奇數因子矛盾。

所以證得如果一個數能夠分解為連續個正整數相加，那么這個數一定包含奇數因子

import java.io.*;
import java.util.*;
public class Main {public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());long res = 0;String[] data = br.readLine().split(" ");for(int i = 0; i < n; i++) {long d = Long.parseLong(data[i]);while(d % 2 == 0) {d /= 2;}if(d == 1) {res++;}}System.out.print(res);br.close();}
}