ぎゃくそすう
920 ワード
ACdreamers神ブログから転載(こちらを押してください)
定義:任意の正の整数xについて、その約数の個数をg(x)と記す.例えばg(1)=1,g(6)=4.ある正の整数xが、任意のi(0性質1:一つの反素数の質因子は必然的に2から連続する質数である.
性質2:p=2^t 1*3^t 2*5^t 3*7^t 4.....必然t 1>=t 2>=t 3>=...
例題:ZOJ 2562
nはnより小さく、因子数が最も多く、値が最も小さい数を求める.
定義:任意の正の整数xについて、その約数の個数をg(x)と記す.例えばg(1)=1,g(6)=4.ある正の整数xが、任意のi(0
性質2:p=2^t 1*3^t 2*5^t 3*7^t 4.....必然t 1>=t 2>=t 3>=...
例題:ZOJ 2562
nはnより小さく、因子数が最も多く、値が最も小さい数を求める.
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
LL prim[]={2,3,5,7,11,13,17,19,23,29,31,37};
LL ans,res,n;
void dfs(int i,LL x,LL num,int limit)
{
if(num>res||(num==res&&ans>x)) ans=x,res=num;
if(i>=12) return ;
for(int k=1;k<=limit;k++){
if(x*prim[i]>n) break;
x*=prim[i];
dfs(i+1,x,num*(k+1),k);///
}
}
int main()
{
while(cin>>n){
ans=n;res=0;
dfs(0,1,1,50);
cout<<ans<<endl;
}
return 0;
}