【BZOJ1053】【HAOI2007】【反素数ant】
2014-03-17 15:59:02| 分类：
AC题目
| 标签：
|举报
|字号大中小 订阅
实际上就是求小于n的因数个数最大的即可，很显然对于反质数，它的因子数个数是单调的，所以咱们相当于求 小于n的最大反质数即可，而小于n的最大反质数实际上就是小于n的因数个数最大的质数。（如果有最大的多个，取最小的）
先有一个组合计数的结论，那就是设 x=p1^y1*p2^y2*p3^y3....那么这个数的因数的个数就是 (y1+1)*(y2+2)*.....，那么咱们就是要求 这样的东西：
p1^y1*p2^y2*p3^y3...<=n
且(y1+1)*(y2+1)*(y3+1)....最大。
首先根号n之后的质数显然不用选（所以只考虑 40000内的质数），然后就是筛素数，大概4204个素数..贪心点选，显然选小的比选大的更优，所以只需要暴力 到29貌似就超10^9方了....（这么好？一开始没想到只需要暴力这么少......以为很多的只想到贪心的那一步，没想到素数这么少...然后在纠结如何DP..然后发现这么少囧）
2,3,5,7,11,13,17,19,23,29,10个质数，小学题目啦咩....直接上暴力就可以了，大概 logN^10，实际上应该比这个少蛮多的....再加上一点剪枝就可以了。（比如指数应该是单调递减的，因为把大的质数的指数加到另外一个显然不差）========================================
var n:int64;
a:array[1..10]of longint=(2,3,5,7,11,13,17,19,23,29);
ans,max:int64;
function cal(n,p:longint):int64;
var i:longint;
begin
if p=0 then exit(1) else exit(n);
end;
procedure dfs(now,num:int64;kth:longint;var max,ans:int64);
var i:longint;
s:int64;
begin
if kth=11 then
begin
if num=max then
if ans>now then
ans:=now;
if num>max then
begin
ans:=now;
max:=num;
end;
exit;
end;
i:=0;
s:=now;
while (s*cal(a[kth],i)<=n) do
begin
s:=s*cal(a[kth],i);
dfs(s,num*(i+1),kth+1,max,ans);
inc(i);
end;
end;
procedure init;
begin
read(n);
max:=0;
dfs(1,1,1,max,ans);
write(ans);
end;
begin
init;
end.
评论这张
转发至微博
转发至微博
关闭
玩LOFTER，免费冲印20张照片，人人有奖！
我要抢>
<#--最新日志，群博日志-->
<#--推荐日志-->
<#--引用记录-->
<#--博主推荐-->
<#--随机阅读-->
<#--首页推荐-->
<#--历史上的今天-->
<#--被推荐日志-->
<#--上一篇，下一篇-->
<#-- 热度 -->
<#-- 网易新闻广告 -->
<#--右边模块结构-->
<#--评论模块结构-->
<#--引用模块结构-->
<#--博主发起的投票-->
评论