0 or 1（hdu2608）数学题 0 or 1

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

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

Sample Output

Hint

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

初看这道题目挺简单的不是吗0 or 1，关键是找到解题的入口

现在来分析一下：

【分析】
当N=10；
1
1 2
1 3
1 2 4
1 5
1 2 3 6
1 7
1 2 4 8
1 3 9
1 2 5 10
注意到不要单行相加，按列来加，有10个1，5个2，3个3，2个4和5，1个6，7，8，9，10，
看到这里，我立刻就醒过省来了；
10/1=10，10/10=1，s+=10;
10/2=5，10/5=2,s+=5*2;
10/3=3，10/3=3，s+=3*3;
10/4=2，10/2=5，s+=(4+5)*2;//按区间算；
10/6=1，10/1=10，s+=(6+7+8+9+10)*1;//按区间算；

#include<stdio.h>
int count(int x)
{

    if(x==1)
        return 1;
    int i,j,w,m,s=x;
    for(i=2;i<=x;)
    {
        w=x/i;
        m=x/w;
        if(m==i)
        {
            i++;
            s+=(w*m)%2;
            s%=2;
        }
        else
        {
            int t=(i+m)*(m-i+1)/2;//连续区间，等差求和；(6+10)*(10-6+1)/2;
            s+=(t*w)%2;
            s%=2;
            i=m+1;//令i=x+1，退出；
        }
    }
    return s;
}
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%d
",count(n));
    }
    return 0;
}

看了网上的另一种算法，发现代码更简洁思路更清晰，但是时间比我代码久，

分析是这样的；

分析:假设数n=2^k*p1^s1*p2^s2*p3^s3*...*pi^si;//k,s1...si>=0,p1..pi为n的素因子
所以T[n]=(2^0+2^1+...+2^k)*(p1^0+p1^1+...+p1^s1)*...*(pi^0+pi^1+...+pi^si);
显然(2^0+2^1+...+2^k)%2=1,所以T[n]是0或1就取决于(p1^0+p1^1+...+p1^s1)*...*(pi^0+pi^1+...+pi^si)
而p1...pi都是奇数(除2之外的素数一定是奇数),所以(pi^0+pi^1+...+pi^si)只要有一个si为奇数(i=1...i)
则(pi^0+pi^1+...+pi^si)%2=0,则T[n]%2=0//若si为奇数,则pi^si+1为偶数,pi^1+pi^2+...+pi^(si-1)为偶数(偶数个奇数和为偶数)
所以要T[n]%2=1,则所有的si为偶数，则n=2^(k%2)*m^2;//m=2^(k/2)*p1^(s1/2)*p2^(s2/2)*...*pi^(si/2)
所以只要n为某个数的平方或者某个数的平方和则T[n]%2=1,只要统计n的个数即可

简而言之：数为1的是某数的平方或某数平方的2倍，之前结果之和取余

 1 #include <stdio.h>
 2 #include<math.h>
 3 int main()
 4 {
 5     int t,sum;
 6     __int64 n,i,k;
 7     scanf("%d",&t);
 8     while(t--)
 9     {
10         scanf("%I64d",&n);
11         sum=k=(int) sqrt(n);//前面有几个平方
12         for(i=1;i<=k;i++)
13         {
14             if(i*i*2<=n)
15                 sum++;
16         }
17         sum=sum%2;
18         printf("%d
",sum);
19     }
20     return 0;
21 }

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int t,n;
10     cin>>t;
11     while(t--)
12     {
13         cin>>n;
14         int sum=(int)sqrt(n*1.0)+(int)sqrt(n*1.0/2);
15         cout<<sum%2<<endl;
16     }
17     return 0;
18 }

View Code

0 or 1（hdu2608）数学题 0 or 1

相关推荐