51nod 1060 最复杂的数 反素数

时间：2024-08-16 19:04:50

1060 最复杂的数

基准时间限制：1 秒 空间限制：131072 KB
把一个数的约数个数定义为该数的复杂程度，给出一个n，求1-n中复杂程度最高的那个数。
例如：12的约数为：1 2 3 4 6 12，共6个数，所以12的复杂程度是6。如果有多个数复杂度相等，输出最小的。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 100)

第2 - T + 1行：T个数，表示需要计算的n。（1 <= n <= 10^18)
Output
共T行，每行2个数用空格分开，第1个数是答案，第2个数是约数的数量。
Input示例
5

1

10

100

1000

10000
Output示例
1 1

6 4

60 12

840 32

7560 64
思路：反素数深搜；
acdream反素数：反素数深度分析超时原因：同样的道理，如果51nod 1060 最复杂的数  反素数，那么必有51nod 1060 最复杂的数  反素数
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define esp 0.00000000001

#define pi 4*atan(1)

const int N=1e5+,M=2e7+,inf=1e9+,mod=1e9+;

const ll INF=1e18;

int p[N]={,,,,,,,,,,,,,,,};

ll x;

ll num,hh;

void dfs(int pos,ll ans,ll sum,int pre)

{

    if(pos>)

    return;

    if(hh<sum)

    {

        num=ans;

        hh=sum;

    }

    else if(hh==sum)

        num=min(ans,num);

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

    {

        if(x/ans<p[pos])break;

        dfs(pos+,ans*=p[pos],sum*(i+),i);

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%lld",&x);

        num=INF;

        hh=;

        dfs(,,,);

        printf("%lld %lld\n",num,hh);

    }

    return ;

}






相关文章