Sigma Function

今天药忘吃喽~ 2022-07-29 09:24 150阅读 0赞

Sigma Function ：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=109329\#problem/C][http_acm.hust.edu.cn_vjudge_contest_view.action_cid_109329_problem_C] 密码：nefu

题目大意：已知Sigma函数表示的是该数的所有因子的和，要求出从1到n，Sigma函数的值为偶数的数的个数。

PC-大致分析：由于n比较大，从1到n遍历肯定会超时，而且对于每一个i都要进行判断其Sigma函数是否为偶数，但是现在能处理的就是先尝试着计算一下当n的值比较小的时候的Sigma函数为偶数的情况，具体实现就是先筛一遍素数（由于n为 10^12 ，所以筛素数的范围在10^6 即可），然后再对n进行素因子分解，对于每个因子，Sigma函数中连乘的每一项如果出现一个偶数，那么整个Sigma函数就是偶数（根据偶数X偶数=偶数，奇数X偶数=偶数，奇数X奇数=奇数）。当然这个算法会TLE ，但是会找到一些规律。

代码实现如下：（TLE代码）

#include <iostream>
    #include <stdio.h>
    #include <math.h>
    #include <string.h>
    
    using namespace std;
    const int MAXN=1000100;
    const int MAXN1=1000000;
    bool isprime[MAXN];
    int prime[MAXN];
    
    void getprime()
    {
        int nprime=0;
        for(long long i=2;i<MAXN1;i++)
        {
            if(!isprime[i])
            {
                prime[nprime++]=i;
                for(long long j=i*i;j<MAXN1;j+=i)
                {
                    isprime[i]=true;
                }
            }
        }
    }
    
    int factor[100][2];
    int cnt;
    int getfactor(long long n)
    {
        long long tmp=n;
        cnt=0;
        memset(factor,0,sizeof(factor));
        for(int i=0;prime[i]*prime[i]<=tmp;i++)
        {
            factor[cnt][1]=0;
            if(tmp%prime[i]==0)
            {
                factor[cnt][0]=prime[i];
                while(tmp%prime[i]==0)
                {
                    factor[cnt][1]++;
                    tmp/=prime[i];
                }
                cnt++;
            }
        }
        if(tmp!=1)
        {
            factor[cnt][0]=tmp;
            factor[cnt++][1]=1;
        }
        return cnt;
    }
    
    int main()  //打表
    {
        int t;
        long long sum;
        long long n;
        int casenum=0;
        getprime();
        scanf("%d",&t);
        while(t--)
        {
    
            sum=0;
            scanf("%lld",&n);
            for(long long i=2;i<=n;i++)
            {
                int k=getfactor(i);
                int flag=0;
                for(int j=0;j<k;j++)
                {
                    if(((int)(pow(factor[j][0],(factor[j][1]+1))-1)/(factor[j][0]-1))%2==0)
                    {
                        flag=1;
                        break;
                    }
                }
                if(flag==1)
                {
                    cout<<i<<"sigma是偶数"<<endl;
                    sum++;
                }
            }
            printf("Case %d: %lld\n",++casenum,sum);
        }
        return 0;
    }

代码输出如下：

4
    100
    3sigma是偶数
    5sigma是偶数
    6sigma是偶数
    7sigma是偶数
    10sigma是偶数
    11sigma是偶数
    12sigma是偶数
    13sigma是偶数
    14sigma是偶数
    15sigma是偶数
    17sigma是偶数
    19sigma是偶数
    20sigma是偶数
    21sigma是偶数
    22sigma是偶数
    23sigma是偶数
    24sigma是偶数
    26sigma是偶数
    27sigma是偶数
    28sigma是偶数
    29sigma是偶数
    30sigma是偶数
    31sigma是偶数
    33sigma是偶数
    34sigma是偶数
    35sigma是偶数
    37sigma是偶数
    38sigma是偶数
    39sigma是偶数
    40sigma是偶数
    41sigma是偶数
    42sigma是偶数
    43sigma是偶数
    44sigma是偶数
    45sigma是偶数
    46sigma是偶数
    47sigma是偶数
    48sigma是偶数
    51sigma是偶数
    52sigma是偶数
    53sigma是偶数
    54sigma是偶数
    55sigma是偶数
    56sigma是偶数
    57sigma是偶数
    58sigma是偶数
    59sigma是偶数
    60sigma是偶数
    61sigma是偶数
    62sigma是偶数
    63sigma是偶数
    65sigma是偶数
    66sigma是偶数
    67sigma是偶数
    68sigma是偶数
    69sigma是偶数
    70sigma是偶数
    71sigma是偶数
    73sigma是偶数
    74sigma是偶数
    75sigma是偶数
    76sigma是偶数
    77sigma是偶数
    78sigma是偶数
    79sigma是偶数
    80sigma是偶数
    82sigma是偶数
    83sigma是偶数
    84sigma是偶数
    85sigma是偶数
    86sigma是偶数
    87sigma是偶数
    88sigma是偶数
    89sigma是偶数
    90sigma是偶数
    91sigma是偶数
    92sigma是偶数
    93sigma是偶数
    94sigma是偶数
    95sigma是偶数
    96sigma是偶数
    97sigma是偶数
    99sigma是偶数
    Case 1: 83

经过总结和归纳，得到规律：Sigma函数为偶数的个数比较多，但是为奇数的个数比较少，而且只有x^2 , 2\*x^2 , 2^x 时，其Sigma函数才为奇数，这样我们可以用去掉奇数的方法，来求出偶数的个数。  
具体去掉这三种情况的方法要考虑用到容斥原理，因为两者之间可能会有重复的。

设n中有t1个x^2，则t1=sqrt(n);（自动向下取整了）

设n中有t2个2\*x^2，则t2=sqrt(n/2); （自动向下取整了） //t1与t2之间不会有重复的元素

设n中有t3个2^x，则 ![Center][] ，即 x\*ln(2)<=ln(n)，则t3=ln(n)/ln(2.0);

设n中有t4个x^2=2\*2^x ，则重复的值有2^1，2^3，2^5，……即指数为奇数的都会重复，则t4的个数和t3有关，即 t4=(t3+1)/2;

设n中有t5个x^2=2^x ，则重复的值有2^0，2^2，2^4，……即指数为偶数的都会重复，则t5的个数和t3也有关，即t5=t3/2;

综上，所有偶数的个数即为：n-t1-t2-t3+t4+t5;

代码实现如下：

#include <iostream>
    #include <stdio.h>
    #include <math.h>
    
    using namespace std;
    
    int main()
    {
        int T;
        int casenum;
        casenum=0;
        long long n;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%lld",&n);
            if(n==1)
            {
                printf("Case %d: ",++casenum);
                printf("0\n");
            }
            else
            {
                long long t1=sqrt(n*1.0);
                long long t2=sqrt(n*1.0/2);
                long long t3=log(n*1.0)/log(2.0);
                long long t4=(log(n*1.0)/log(2)+1)/2;
                long long t5=t3/2;
                //long long t5=log(t1*1.0)/log(2.0);
                long long sum=n-t1-t2-t3+t4+t5;
                printf("Case %d: %lld\n",++casenum,sum);
            }
        }
        return 0;
    }

另一种方法：

徒手解释：

![Center 1][]

代码实现：

#include <iostream>
    #include <stdio.h>
    #include <math.h>
    
    using namespace std;
    
    long long ds[100];
    const long long MAXN=1000000000005;
    int ff()
    {
        int cnt=1;
        ds[0]=1;
        while(1)
        {
            ds[cnt]=ds[cnt-1]*2;
            if(ds[cnt]>MAXN)
            break;
            cnt++;
        }
        return cnt;
    }
    int main()
    {
        int T;
        int casenum=0;
        long long n;
        scanf("%d",&T);
        int k=ff();
        while(T--)
        {
            scanf("%lld",&n);
            long long sum=0;
            for(int i=0;i<k;i++)
            {
                if(ds[i]>n) break;
                sum+=((long long)sqrt((n/ds[i])+0.5)+1)/2;
            }
            printf("Case %d: %lld\n",++casenum,n-sum);
        }
        return 0;
    }

[http_acm.hust.edu.cn_vjudge_contest_view.action_cid_109329_problem_C]: http://http://acm.hust.edu.cn/vjudge/contest/view.action?cid=109329#problem/C
[Center]: /images/20220728/3385f767b2e349d8baeaa36a09a6ca4d.png
[Center 1]: /images/20220728/0bab56fe82a3403c82a692162d07e1f0.png