hdu 2608 0 or 1(数论推理)

hdu 2608 0 or 1(数论推理)

题目：​​or 1

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2947    Accepted Submission(s): 795

Problem Description

Solving problem is a interesting thing. Yifenfei like to slove different problem,because he think it is a way let him more intelligent. But as we know,yifenfei is weak in math. When he come up against a difficult math problem, he always try to get a hand. Now the problem is coming! Let we define T(n) as the sum of all numbers which are positive integers can divied n. and S(n) = T(1) + T(2) + T(3)…..+T(n).

Input

The first line of the input contains an integer T which means the number of test cases. Then T lines follow, each line consists of only one positive integers n. You may assume the integer will not exceed 2^31.

Output

For each test case, you should output one lines of one integer S(n) %2. So you may see the answer is always 0 or 1 .

Sample Input

3 1 2 3

Sample Output

Hint

Hint S(3) = T(1) + T(2) +T(3) = 1 + (1+2) + (1+3) = 8

S(3) % 2 = 0

Author

yifenfei

分析：这是我目前见过的最棒的数论题了。数论题就是这样，代码简洁而优雅。

/*在所有的素因子中只有2是偶数，设number=2^p0*k1^p1*k2^p2*……*kn^pn，那么T(n)=(1+2^1+2^2+……+2^p0)*(1+k1^1+……+k1^p1)*……*(1+kn^1+……+kn^pn)因为(1+2^1+2^2+……+2^p0)%2=1，所以问题集中于(1+k1^1+……+k1^p1)*……*(1+kn^1+……+kn^pn) 如果pi是一个奇数那么就有一个式子的结果是偶数（偶数个奇数是偶数）。然后(1+k1^1+……+k1^p1)*……*(1+kn^1+……+kn^pn)%2=0.那么反过来想，所有的pi都是偶数的话(1+k1^1+……+k1^p1)*……*(1+kn^1+……+kn^pn)%2=1（奇数个奇数是奇数，奇数乘以奇数还是奇数），满足条件“所有的pi都是偶数”的数字(1+k1^1+……+k1^p1)*……*(1+kn^1+……+kn^pn)必然是另一个数字的平方。所以number必然是里一个数字的平方（p0是偶数）或者一个数字平方的2倍（p0是奇数）*/#include #include #include using namespace std;int main(){ int t,n; cin>>t; while(t--){ scanf("%d",&n); int res=(int)sqrt(n*1.0)+(int)sqrt(n*1.0/2); printf("%d\n",res%2); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。