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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1853】【SCOI2010】【幸运数字】  

2014-04-02 11:43:56|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     咱是从wsh君那里看到的题目。
     题目大意:求[a,b]间 由6,8构成的数以及其倍数的个数。(a,b<=10^10)
     实际上可以转化成求 【1,a-1】间的和【1,b】间的,用后者减去前者即可。(ps:虽然可以...但是咱这样写就TLE了囧,还是得直接来)
     然后咱们又可以暴力出所有的6,8构成的数(这个2^10),然后问题就是求这些的倍数的个数。这个咱们可以用容斥原理做。咱们要知道一个结论:
     N内a或b的倍数的个数=N/a+N/b-N/lcm(a,b)
     实际上上面的翻译出来就是 a在N以内的倍数+b在N以内的倍数-a,b两个在N以内的相同的倍数(就是LCM开始的)
     同理可以按照容斥原理YY下去。
     N内a1|a2|a3|a4...|an的倍数的个数=∑N/ai-∑N/lcm(ai,aj)+∑N/lcm(ai,aj,ak)...+(-1)^(n-1)/lcm(a1,a2..,an)。
     上面就是答案。但是写裸的很容易TLE...
     下面就是优化。
     优化1:这个的倍数咱们可以暴力用一个DFS枚举下,然后求LCM的时候如果超出了N则强行剪枝即可。咱们可以发现这个剪枝实际上就只算了有用的那些答案,而按这个来看LCM不超过7~8次貌似就可以算完了....
     优化2:咱一开始的DFS是直接枚举所有的状态再做的,实际上这还可以优化,咱们每次枚举的方案只要满足就立刻做即可。
     优化3:非常好的一个优化,那就是把所有的数枚举出来之后再去去掉某些其中本来就是倍数的数。
     把上面三个加上去应该就可以过了。
     然后关于判断 c[i]*lcm/gcd(c[i],lcm)>n可能会在c[i]*lcm上溢,咱们可以两边同除以n,然后变成判断 c[i]/n*lcm/gcd(c[i],lcm)>1,这样用浮点数来算,就避免了上溢问题。
     然后这道题就可以Accept了。
=========================

program bzoj1853;
var a,b,tot:int64;
    sum:int64;
    c:array[0..5028]of int64;
    flag:array[0..5028]of boolean;

procedure qsort(l,r:longint);
var i,j:longint;x,y:int64;
begin
  i:=l;j:=r;
  x:=c[(l+r)shr 1];
  repeat
    while c[i]>x do inc(i);
    while c[j]<x do dec(j);
    if i<=j then
     begin
       y:=c[i];c[i]:=c[j];c[j]:=y;
       inc(i);dec(j);
     end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;

function gcd(a,b:int64):int64;
begin
  if b=0 then exit(a)
  else exit(gcd(b,a mod b));
end;

procedure dfs(p,num:longint;lcm,a,b:int64);
var u,v,w:int64;
    d:double;
begin
  if p>tot then exit;
  dfs(p+1,num,lcm,a,b);
  if flag[p] then exit;
  d:=c[p]/b*lcm/gcd(lcm,c[p]);
  if d-1e-5>1 then exit;
  w:=c[p] div gcd(lcm,c[p])*lcm;
  if num and 1=0 then sum:=sum+(b div w)-((a-1)div w)
                 else sum:=sum-(b div w)+((a-1)div w);
  dfs(p+1,num+1,w,a,b);
end;

procedure find(p:int64);
begin
  if p>b then exit;
  if (p<>0)then
   begin
     inc(tot);
     c[tot]:=p;
   end;
  find(p*10+6);
  find(p*10+8);
end;

procedure init;
var i,j:longint;
begin
  read(a,b);
  tot:=0;
  find(0);
  sum:=0;
  qsort(1,tot);
  fillchar(flag,sizeof(flag),false);
  for i:=1 to tot do
   for j:=i+1 to tot do
    if c[i] mod c[j]=0 then
     begin
       flag[i]:=true;
       break;
     end;
  dfs(1,0,1,a,b);
  write(sum);
end;

begin
  init;
end.



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

历史上的今天

评论

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

页脚

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