題目：0 or 1

?

分析：
?
首先看T(n)，通過找規(guī)律可以發(fā)現(xiàn)：（看了別人的解題報(bào)告才知道這部分是怎么推出來的）
?
僅當(dāng)n為1，2，4，8，9，16，18，25，32，36，49，50，64，72，81，98，100…………的時(shí)候，T(n)%

2==1;
?
可以發(fā)現(xiàn)，if(n%(i*i)==0 || n%(i*i*2)==0) => T(n)%2==1;
?
然后對S(n)，只要看在n前面，有幾個(gè)T(k)是為1即可，
?
即是找有多少個(gè)數(shù)是滿足的即可；
?
我推到這，結(jié)果沒利用找到的規(guī)律求個(gè)數(shù)，而是用了一個(gè)循環(huán)，結(jié)果超時(shí)了~~
?
求個(gè)數(shù)的時(shí)候，其實(shí)可以利用滿足(i*i<=n || i*i*2<=n)這個(gè)關(guān)系式，如下:
?
(int)sqrt(n)+(int)sqrt(n/2.0)
?
看來別人的解題報(bào)告才知道：求T(n)的時(shí)候是這么推出來的：
?
對于T(n)，設(shè)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)；
?
因?yàn)?2^0+2^1+...+2^k)%2==1始終成立，則T(n)%2的結(jié)果取決于(pi^0+pi^1+...+pi^si)%2，只要其中一

個(gè)為0，則T(n)%2==0。所以只要有一個(gè)si為

奇數(shù)時(shí)，T(n)%2==0。即n為2^k*m^2時(shí)，T(n)為1。顯然n也即m^2或2*m^2時(shí)，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; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU2608 0 or 1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。