把一个数的约数个数定义为该数的复杂程度,给出一个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
——————————————————————————
这道题就是求不大于n的反素数 反素数有个性质就是质数的次数
质因数越小出现的次数越大 也就是不增
这样之后找18个质数(乘起来超过1e18) 然后这样剪枝就可以过了
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const LL inf=1LL<<;
LL read(){
LL 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[]={,,,,,,,,,,,,,,,,,};
LL T,n,ans,mx;
void dfs(LL now,LL sum,int step,int last){
if(now>mx) mx=now,ans=sum;
if(now==mx&&ans>sum) ans=sum;
for(int i=;i<=last;i++){
if(inf/num[step]<sum||sum*num[step]>n) break;
sum=sum*num[step];
dfs(now*(i+),sum,step+,i);
}
}
int main(){
T=read();
while(T--){
ans=; mx=;
n=read();
dfs(,,,);
printf("%lld %lld\n",ans,mx);
}
return ;
}