蒟蒻的第二篇题解，虽然第一篇没过。

题目大意

有 $n$ 次询问，每次询问输入一个数，当不可以被拆解成连续自然数相加的和时就删除这个数，最后输出数字还剩多少。

分析

我第一眼看到这道题就想用前缀和做，但是数据范围 $1\le a_i \le 10^{16}$ 毕竟有点太残酷了，并且空间限制才 256MB ，数组要开 long long ，连撑起这个表都不够！更别说时间了！

但是倔强的我还是敲了一遍前缀和代码，荣获 30pts：

#include<bits/stdc++.h>
using namespace std;
int T;
long long qianz[33000000],n,tot;//256MB=256000000B 
int main(){//by Rtaaa
	cin>>T;
	for(int i=1;i<=32999999;i++)qianz[i]=qianz[i-1]+i;//打前缀和数组 
	while(T--){
		bool flag=0;//flag是标记数组，用来标记这个数要不要删 
		scanf("%lld",&n);
		for(int i=1;i<=n;i++){
			for(int j=0;j<i-1;j++){//不能有单独一个数字，所以要<i-1 
				if(n==qianz[i]-qianz[j]){
					flag=1;
					break;
				}
			}
			if(flag==1)break;//优化（虽然说没啥卵用） 
		}
		if(flag==0)tot++;//删除的数字+1 
	}
	cout<<tot;
}

果然不出所料，这道题又是一道找规律题（前缀和都寄了一定是啦），于是我将这个前缀和程序给修改一下，让它输出不能表示为连续自然数相加的和的数字，修改后代码长这个样：

#include<bits/stdc++.h>
using namespace std;
int T;//by Rtaaa
long long qianz[33000000],n,tot;//256MB=256000000B 
int main(){
	for(int i=1;i<=32999999;i++)qianz[i]=qianz[i-1]+i;
	for(int n=1;n<=1000;n++){
		bool flag=0;
		for(int i=1;i<=n;i++){
			for(int j=0;j<i-1;j++){//不能有单独一个数字，所以要<i-1 
				if(n==qianz[i]-qianz[j]){
					flag=1;
					break;
				}
			}
			if(flag==1)break;//优化 
		}
		if(flag==0)cout<<n<<endl;
	}
}

F12 运行，结果出来了：

1
2
4
8
16
32
64
128
256
512

是不是有点熟悉！这就是 $2$ 的幂次方啊！那这样这个程序就简单了！只需要判断是否为 $2$ 的幂次方就行了！

相信不少人已经在写快速幂了，不过这里我介绍一个对于判断 $2$ 的幂次方的黑科技，只需要 $O(1)$ 复杂度！

先贴出来核心代码吧：

bool judge(long long n) {
	return(n&(n-1))==0;//如果是，就返回 true
}

这是为什么呢？我们先来观察 $2$ 的幂次方在二进制情况下的特点：

$1 (2^0) -> 0001$
$2 (2^1) -> 0010$
$4 (2^2) -> 0100$
$8 (2^3) -> 1000$
...

发现规律了吗？当一个数是 $2$ 的幂次方时，它的二进制表示中只有一个 $1$ ，其余都是 $0$。

那么 $n-1$ 又是怎么回事呢？对于一个是 $2$ 的幂次方的数 $n$，$n - 1$ 会将那个唯一的 $1$ 变成 $0$，并将其右侧的所有 $0$ 变成 $1$。例如 $n=8(1000)$ 时，$n-1=7(0111)$，的确符合这一规律，当把这两个数按照位与运算时，答案就是 $0$。所以这个函数的意思就是如果这个数是 $2$ 的幂次方，那么就返回 true

特别注意的是，位运算的级别比较低，需要带括号哦~

代码

下面就是大家喜闻乐见的代码环节了！

#include<bits/stdc++.h>
using namespace std;
long long a,tot,T;
bool judge(long long n) {
	return (n&(n-1))==0;//如果是，就返回 true
}
int main(){//by Rtaaa
	cin>>T;
	while(T--){
		scanf("%lld",&a);
		if(judge(a))tot++;//是2的幂次方就扔掉 
	}
	cout<<tot;
}