数论+深搜luoguP4397聪明的燕姿

作者: 不给赞就别想跑哼 | 来源:发表于2018-10-10 20:43 被阅读0次

    题目背景
    阴天傍晚车窗外
    未来有一个人在等待
    向左向右向前看
    爱要拐几个弯才来
    我遇见谁会有怎样的对白
    我等的人他在多远的未来
    我听见风来自地铁和人海
    我排着队拿着爱的号码牌

    题目描述
    城市中人们总是拿着号码牌,不停寻找,不断匹配,可是谁也不知道自己等的那个人是谁。

    可是燕姿不一样,燕姿知道自己等的人是谁,因为燕姿数学学得好!燕姿发现了一个神奇的算法:假设自己的号码牌上写着数字 S,那么自己等的人手上的号码牌数字的所有正约数之和必定等于 S。

    所以燕姿总是拿着号码牌在地铁和人海找数字(喂!这样真的靠谱吗)可是她忙着唱《绿光》,想拜托你写一个程序能够快速地找到所有自己等的人。

    输入输出格式
    输入格式:
    输入包含 k 组数据。 对于每组数据,输入包含一个号码牌S。

    输出格式:
    对于每组数据,输出有两行,第一行包含一个整数 m,表示有 m 个等的人。

    第二行包含相应的 m 个数,表示所有等的人的号码牌。

    注意:你输出的号码牌必须按照升序排列。

    一个正整数n可以被分成p1a1*p2a2p3^a3pn^an;

    piai的正约数个数为ai+1,即1,pi1,pi2,pi3,....,pi^ai,所以n的正约数个数为(a1+1)(a2+1)(a3+1)...(an+1);

    实际上n的约数是在p1a1、p2a2、...、pk^ak每一个的约数中分别挑一个相乘得来,

    可知共有(a₁+1)(a₂+1)(a₃+1)…(ak+1)种挑法,即约数的个数。

    由[乘法原理]可知它们的和为

    f(n)=(p10+p11+p12+…p1a1)(p20+p21+p22+…p2a2)…(pk0+pk1+pk2+…pkak)

    于是乎就有了搜索策略,搜索p,并枚举他的幂次,满足一下两个条件即为满足解

    ①最后分解完,剩余得1,将所得结果记录②分解剩余的数-1是一个质数p,这样就可以看成p0+p1,也可以得到结果,将其记录
    代码如下

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #define LL long long
    #include<algorithm>
    using namespace std;
    int prime[50010],vis[50010],cnt,ans[100010],cnt1;
    LL s;
    void GetPrime(){
        memset(vis,1,sizeof(vis));
        for(int i=2;i<=50000;i++){
            if(!vis[i]) continue;
            prime[++cnt]=i;
            for(int j=2;j<=50000/i;j++) vis[i*j]=0; 
        }
    } 
    int check_prime(LL x){
        if(x<=50000&&vis[x]==0) return 0;
        for(int i=1;prime[i]*prime[i]<=x;i++) if(x%prime[i]==0) return 0;
        return 1;
    }
    void dfs(LL now,int last,LL left){
        if(left==1){//情况1
            ans[++cnt1]=now;
            return;
        }
        if(left-1>prime[last]&&check_prime(left-1)) ans[++cnt1]=now*(left-1);//情况2
        for(int i=last+1;prime[i]*prime[i]<=left;i++) 
            for(LL temp=prime[i]+1,t=prime[i];temp<=left;t*=prime[i],temp+=t) if(left%temp==0) dfs(now*t,i,left/temp);      
    }
    int main(){
        GetPrime();
        while(scanf("%lld",&s)!=EOF){
            cnt1=0;
            dfs(1,0,s);
            sort(ans+1,ans+cnt1+1);
            printf("%d\n",cnt1);
            for(int i=1;i<=cnt1;i++){
                if(i==cnt1) printf("%d\n",ans[i]);
                else printf("%d ",ans[i]);
            }
        }
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:数论+深搜luoguP4397聪明的燕姿

        本文链接:https://www.haomeiwen.com/subject/rqmmaftx.html