背景
蛟川书院模拟试题
描述
TOM有一个无穷序列中如下:
110100100010000100000。。。。。
请你帮助TOM找出在这个无穷序列中指定位置上的数字
110100100010000100000。。。。。
请你帮助TOM找出在这个无穷序列中指定位置上的数字
输入格式
第一行一个正整数N,表示询问的次数;
接下来的N行一个正整数Ai,Ai表示在序列中的位置。
接下来的N行一个正整数Ai,Ai表示在序列中的位置。
输出格式
N行,每一行为0或1,表示序列第Ai位上的数字。
测试样例1
输入
4
3
14
7
6
输出
0
0
1
0
备注
对于100%的数据有N<=1500000,Ai<=10^9
提示:差值为1的等差数列 Sn(前n项和)=n(n+1)/2
Moe-ing
提示:差值为1的等差数列 Sn(前n项和)=n(n+1)/2
Moe-ing
思路:这题数据有点大,不考虑用模拟出整个序列再求,可以找出这个序列的规律,在对其进行计算。
过程:可以先对于2*(a-1+0.25)进行开方,并取整,再用a-sum*(sum-1)/2;,这样就可以知道那一位是不是1或者0。
代码如下:
#include<stdio.h>
#include<math.h>
int main()
{
int a,sum,n;
scanf("%d",&n);
while(n--)
{
scanf("%d",&a);
sum=0.5+sqrt(0.25+*(a-));//对于2*(a-1+0.25)进行开方,并取整
a=a-sum*(sum-)/;
if(a==)printf("%d\n",);//是1
else printf("%d\n",);//否则是0
}
return ;
}