Pairs Forming LCM 素数筛和素因子分解

本是古典何须时尚 2022-07-29 08:50 162阅读 0赞

Pairs Forming LCM ：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=109329\#problem/B][http_acm.hust.edu.cn_vjudge_contest_view.action_cid_109329_problem_B] 密码：nefu

一个题目分了好几波才把它完全搞明白，公式还是很多的，直接偷懒上手写了。

![Center][]

![Center 1][]

![Center 2][]

这次写的也是比较啰嗦，但却是自己的思路，先来两个素数筛的代码，再贴上素因子分解的代码，最后才是本题的AC代码哟~

素数筛一：

void getprime1()
    {
        memset(prime,0,sizeof(prime));
        for(int i=2;i<MAXN1;i++)
        {
            if(!prime[i])
            prime[++prime[0]]=i;
            for(int j=1;j<=prime[0]&&prime[j]<=MAXN1/i;j++)
            {
                prime[prime[j]*i]=1;
                if(i%prime[j]==0)
                break;
            }
        }
    }

素数筛二：

void getprime()
    {
        memset(isprime,true,sizeof(isprime));
        int nprime=0;
        isprime[1]=0;
        for(long long i=2;i<MAXN;i++)
        {
            if(isprime[i])
            {
                prime[++nprime]=i;  //从下标为1开始使用
                for(long long j=i*i;j<MAXN;j+=i)
                {
                    isprime[j]=false;
                }
            }
        }
    }

需要注意的是，方法二比方法一更优一些，此题必须用方法二，否则会超时。

素因子分解：

long long factor[10010];
    int cnt;
    int getfactors(long long x)
    {
        cnt=0;
        long long tmp=x;
        for(int i=1;prime[i]<=tmp/prime[i];i++)  //从下标1开始使用素数数组
        {
            factor[cnt]=0; //从下标0开始存储每一个素数的指数
            if(tmp%prime[i]==0)
            {
                while(tmp%prime[i]==0)
                {
                    factor[cnt]++;
                    tmp/=prime[i];
                }
                cnt++;
            }
        }
        if(tmp!=1)
        {
            factor[cnt++]=1;
        }
        return cnt;
    }

最终代码实现：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    const int MAXN=10000100;
    const int MAXN1=1000000;
    bool isprime[MAXN];
    int prime[MAXN/10];
    
    void getprime()
    {
        memset(isprime,true,sizeof(isprime));
        int nprime=0;
        isprime[1]=0;
        for(long long i=2;i<MAXN;i++)
        {
            if(isprime[i])
            {
                prime[++nprime]=i;  //从下标为1开始使用
                for(long long j=i*i;j<MAXN;j+=i)
                {
                    isprime[j]=false;
                }
            }
        }
    }
    
    void getprime1()
    {
        memset(prime,0,sizeof(prime));
        for(int i=2;i<MAXN1;i++)
        {
            if(!prime[i])
            prime[++prime[0]]=i;
            for(int j=1;j<=prime[0]&&prime[j]<=MAXN1/i;j++)
            {
                prime[prime[j]*i]=1;
                if(i%prime[j]==0)
                break;
            }
        }
    }
    
    long long factor[10010];
    int cnt;
    int getfactors(long long x)
    {
        cnt=0;
        long long tmp=x;
        for(int i=1;prime[i]<=tmp/prime[i];i++)  //从下标1开始使用素数数组
        {
            factor[cnt]=0; //从下标0开始存储每一个素数的指数
            if(tmp%prime[i]==0)
            {
                while(tmp%prime[i]==0)
                {
                    factor[cnt]++;
                    tmp/=prime[i];
                }
                cnt++;
            }
        }
        if(tmp!=1)
        {
            factor[cnt++]=1;
        }
        return cnt;
    }
    
    int main()
    {
        int t,casenum;
        casenum=0;
        long long n;
        long long sum;
        getprime();
        scanf("%d",&t);
        while(t--)
        {
            scanf("%lld",&n);
            sum=1;
            int k=getfactors(n);
            for(int i=0;i<k;i++)
            {
                sum*=(2*factor[i]+1);
            }
            sum=(sum+1)/2;
            printf("Case %d: %lld\n",++casenum,sum);
        }
        return 0;
    }

[http_acm.hust.edu.cn_vjudge_contest_view.action_cid_109329_problem_B]: http://http://acm.hust.edu.cn/vjudge/contest/view.action?cid=109329#problem/B
[Center]: /images/20220728/04d90f879cfd4865aff6bfbda9094dc9.png
[Center 1]: /images/20220728/958c89be70db4871a125c3c64633ba18.png
[Center 2]: /images/20220728/f83b2728a23d412f9075dabcaf11bb22.png