51nod 1087 1 10 100 1000

1,10,100,1000...组成序列1101001000...，求这个序列的第N位是0还是1。

 收起

 

输入

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行1个数N。（1 <= N <= 10^9)

输出

共T行，如果该位是0，输出0，如果该位是1，输出1。

输入样例

3
1
2
3

输出样例

1
1
0



找出所有的1的位置，然后二分查找。
代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;
int ans[50000],c;
int check(int n) {
    int l = 0,r = c - 1;
    while(l < r) {
        int mid = (l + r + 1) / 2;
        if(ans[mid] > n) r = mid - 1;
        else l = mid;
    }
    return ans[l] == n ? 1 : 0;
}
int main() {
    for(int i = 1,j = 1;i <= 1000000000 - j;j += i ++) {
        ans[c ++] = j;
    }
    int t,n;
    scanf("%d",&t);
    for(int i = 0;i < t;i ++) {
        scanf("%d",&n);
        printf("%d
",check(n));
    }
}