分析:
首先看T(n),通过找规律可以发现:(看了别人的解题报告才知道这部分是怎么推出来的)
仅当n为1,2,4,8,9,16,18,25,32,36,49,50,64,72,81,98,100…………的时候,T(n)%
2==1;
可以发现,if(n%(i*i)==0 || n%(i*i*2)==0) => T(n)%2==1;
然后对S(n),只要看在n前面,有几个T(k)是为1即可,
即是找有多少个数是满足的即可;
我推到这,结果没利用找到的规律求个数,而是用了一个循环,结果超时了~~
求个数的时候,其实可以利用满足(i*i<=n || i*i*2<=n)这个关系式,如下:
(int)sqrt(n)+(int)sqrt(n/2.0)
看来别人的解题报告才知道:求T(n)的时候是这么推出来的:
对于T(n),设n=2^k*p1^s1*p2^s2*...*pm^sm,则T(n)=(2^0+2^1+...+2^k)*(p1^0+p1^1+...+p1^s1)
*...*(ps^0+ps^1+...+ps^sm);
因为(2^0+2^1+...+2^k)%2==1始终成立,则T(n)%2的结果取决于(pi^0+pi^1+...+pi^si)%2,只要其中一
个为0,则T(n)%2==0。所以只要有一个si为
奇数时,T(n)%2==0。即n为2^k*m^2时,T(n)为1。显然n也即m^2或2*m^2时,T(n)为1。
#include <stdio.h>
#include <math.h>
int main()
{
int n,count,cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
count=(int)sqrt(n)+(int)sqrt(n/2.0);
printf("%d\n",count%2);
}
return 0;
}
标签:ps,HDU2608,p1,int,sqrt,pi,+...+ From: https://blog.51cto.com/u_16146153/6388746