洛谷P1795无穷的序列[NOI导刊]
1605+
作者：crxis 发布：2021-05-09 分类：哈希表
题目大意：一个01序列，第1、2、4、7、11……位是1，其他位是0，先有多个询问，请回答第k为上的数字是多少？
题目描述
有一个无穷序列如下：
110100100010000100000…
请你找出这个无穷序列中指定位置上的数字
输入输出格式
输入格式
第一行一个正整数N，表示询问次数；
接下来的N行每行一个正整数Ai，Ai表示在序列中的位置。
输出格式
N行，每行为0或1，表示序列第Ai位上的数字。
输入输出样例
输入样例 #1
4
3
14
7
6
输出样例 #1
0
0
1
0
说明
对于100%的数据有N≤1500000，Ai≤10^9
解题思路
预处理出$10^9$以内所有1的位置，用哈希表存储起来，对于每个查询，若在哈希表中能查到，输出1，否则输出0。
其他方法：对于每个询问，看起是否1+2+3+…的和，如果n*(n+1)/2+1=k有解即输出1，否则输出0；采用离线形式，先对询问排序，再记录答案，可以避免哈希。
程序实现
