首页 > 其他分享 >HDU2608 0 or 1

HDU2608 0 or 1

时间:2023-05-31 18:36:59浏览次数:43  
标签:ps HDU2608 p1 int sqrt pi +...+


题目:0 or 1

 

分析:
 
首先看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

相关文章