注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1053】【HAOI2007】【反素数ant】  

2014-03-17 15:59:02|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    实际上就是求小于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.

     
  评论这张
 
阅读(48)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017