洛谷 P1463 [SDOI2005]反素数ant && codevs2912反素数

题目描述

对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。

如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。

现在给定一个数N，你能求出不超过N的最大的反质数么？

输入输出格式

输入格式：

一个数N（1<=N<=2,000,000,000）。

输出格式：

不超过N的最大的反质数。

输入样例#1：

输出样例#1：

840

这道题很明显要找到的是不大于n的约数数最多的数里面最小的
因为如果约数相同而另一个数比你小就不满足题意了
我们可以把一个数拆成一堆质因数的幂的和 S=2^x1+3^x2+...+p^xn(p仍旧为质数）
方案总数就是cnt=(x1+1)*(x2+1)*(x3+1)*…… 这个自己想想就知道了的
而我们只需要找前9个质数就好了因为前9个质数2*3*5*7*11*13*17*19*23*29=6,469,693,230>2,000,000,000
这样情况其实很少我们只需要来一次爆搜解决问题就好了哇

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int num[]={,,,,,,,,,,,,};

int n,ans,mx;

void dfs(LL now,LL sum,int step){

    if(now>mx) mx=now,ans=sum;

    if(now==mx&&ans>sum) ans=sum;

    for(int i=;i<=;i++){

        if(sum*num[step]>n) break;

        sum=sum*num[step];

        dfs(now*(i+),sum,step+);

    }

}

int main()

{

    n=read();

    ans=;

    dfs(,,);

    printf("%d\n",ans);

    return ;

}

巴特西

洛谷 P1463 [SDOI2005]反素数ant && codevs2912反素数

题目描述

输入输出格式

最新文章

热门文章