首页 > 其他 > 详细

P1463 反素数

时间:2019-09-11 00:30:28      阅读:97      评论:0      收藏:0      [点我收藏+]

题面:https://i.cnblogs.com/EditPosts.aspx?opt=1

前置知识:g(x)=(a1+1)(a2+1)...(an+1),注意:这里p1^a1*p2^a2*...*pn^an=x,且p1,p2,...,pn均为质数
本题直接枚举每个质因子的指数个数即可,然后dfs搜索最大的反素数.

Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<map>
using namespace std;
long long p[20]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
long long n,maxn=-1,ans=-1;
void solve(long long tot,long long x,long long t,long long now){
    if(t>maxn||(t==maxn&&tot<ans)){
        ans=tot;
        maxn=t;
    }
    long long i=tot,j=0,nt=0;
    while(j<now){
        j++;
        if(n/i<p[x]){
            break;
        }
        nt=t*(j+1);
        i*=p[x];
        if(i<=n){
            solve(i,x+1,nt,j);
        }
    }
}
int main(){
    scanf("%lld",&n);
    solve(1,1,1,30);
    printf("%lld",ans);
    return 0;
}

P1463 反素数

原文:https://www.cnblogs.com/ukcxrtjr/p/11503992.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!