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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj2301】【HAOI2011】【Problem b】  

2014-05-01 10:11:22|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:n次询问,每一次询问有多少数对(x,y)满足a<=x<=b,c<=y<=d,gcd(x,y)=k。a,b,c,d,k已经给出。
   a,b,c,d,k,n<=50000。

   首先容易想到,实际上问题可以转化成求 [1,b]和[1,d],[1,a]和[1,c],[1,a]和[1,d],[1,b]和[1,c]四个区间gcd(x,y)=k的,然后容斥原理直接做即可。0.0
   然后gcd(x,y)=k可以转化成gcd(x/k,y/k)=1,在n/k和m/k的范围内。
   那么咱们的问题实际上就是转化成了求 1<=x<=m,1<=y<=n 的gcd(x,y)=k的个数即可。做四次然后容斥搞。
   这个貌似咱们会做了额...莫比乌斯反演搞一搞就可以了...但是!,那个的复杂度是O(max(a,b,c,d)/k)的!,如果都取极限数据的话50000个询问显然会O(n^2)从而TLE....所以咱们这里需要考虑一下如何优化额 0.0
   咱反正是想了半天不知道怎么优化额...【太弱了咩= =】

   神犇A君:我有特别的优化技巧!
   神犇B君:这道题是原题啊2333!
   2333333....
   然后咱就直接发原题链接了= =【POI XIV一题
   优化的关键在于这里,最后的答案显然都是这样的形式:ans=∑miu[i]*(m/i)*(n/i),实际上这里存在一个冗余...咱们首先证明 m/i(i取遍1~m) 最多只有  O(sqrt(m)) 种取法,其中/为除,取整除法的那种。
   一开始没想出来...跑去问叉姐一行神犇= =然后被虐傻了...
   其实非常单纯的证明额...当d<=sqrt(m)的时候,最多有sqrt(m)种组合【显然的吧...】,然后当d>sqrt(m)的时候,m/d就在sqrt(m)内部了,所以还是sqrt(m)的...
   所以总的就是O(sqrt(m))的了= =。
   明明是非常单纯的证法...听完就觉得自己太弱了...
   
   然后由于是连续的区间,所以显然 m/i,n/i所有的相同的连续区间最多有O(sqrt(m)+sqrt(n))种。
   然后咱们处理下莫比乌斯函数的前缀和,就可以将a,b按连续区间分块,然后计算的时候按块来,复杂度就是O(sqrt(m)+sqrt(n))

   但是---------咱们还是得处理出那个a,b的所有的分块的区间来额...不然复杂度还是不会变。咱们只需要保证得到了某一个区间能够在O(1)求出下一个区间即可,这样子就可以保证复杂度是O(sqrt(m)+sqrt(n))不变。这样子最后的复杂度就是O(n(sqrt(a)+sqrt(b))),对于5*10^4还是可以过的。但是...咱们还是不知道怎么O(1)的球区间...实际上这也好考虑...咱们先来考虑对于单个m,怎么求出连续的区间。假设某个值j的连续的区间的开头是i,即m/i=j,i是所有满足条件的i的第一个,那么咱们就考虑最后一个是多少,它是可以求出来的,就是 m/(m/i),这里的/为整除。至于为什么是这个,咱们可以证明出来,咱们设m/i=j,则 j*i+k=m,当咱们增加i的时候,j*(i+1)+k'=m,则k变成k-j,然后一直到k变成负数之前都是可行的,而达到负数的时候实际上是k'<j的时候,这个时候的i实际上就是 m/j,即 m/(m/i)
   所以咱们从1,1开始,每一次挑出min(n/(n/i),m/(m/i)),结合当前的区间就是答案。复杂度为O(N(sqrt(a)+sqrt(b))),这里预处理出miu函数的前缀和,只需要O(n)即可。

  另外...这题学习到了又一个东西= =那就是能用longint的地方不要用int64,尤其是在卡时间的时候最重要的= =这道题调了半天常数终于过去了。还有一个优化是BLADEVIL神犇提出来的,咱们可以在中途使用longint计算,然后赋值给int64的时候可能会越界,这个时候咱们使用一种强制转换的函数,即 int64(),括弧里面是一个变量,能将某个变量在运算中强制变成某个类型,这样子的话速度貌似可以更快!

=================================

program bzoj2301;
const maxn=50010;
var p,miu:array[0..maxn]of longint;
    v:array[0..maxn]of boolean;
    sum:array[0..maxn]of int64;
    a,b,c,d,k,n:longint;
    ans:int64;

function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;

procedure prepare;
var i,j:longint;
begin
  fillchar(v,sizeof(v),true);
  miu[1]:=1;p[0]:=0;
  for i:=2 to 50000 do
   begin
     if v[i] then
      begin
        inc(p[0]);p[p[0]]:=i;
        miu[i]:=-1;
      end;
     for j:=1 to p[0] do
      begin
        if i*p[j]<=50000 then v[i*p[j]]:=false;
        if i*p[j]>50000 then break;
        if i mod p[j]=0 then
         begin
           miu[i*p[j]]:=0;
           break;
         end
        else miu[i*p[j]]:=-miu[i];
      end;
   end;
  fillchar(sum,sizeof(sum),0);
  for i:=1 to 50000 do
    sum[i]:=miu[i]+sum[i-1];
end;

function calc(n,m:longint):longint;
var tt,i,ans,tmp:longint;
begin
  if n>m then
   begin
     tt:=n;n:=m;m:=tt;
   end;
  i:=1;ans:=0;
  while i<=n do
   begin
     tmp:=min(n div (n div i),m div (m div i));
     ans:=ans+(sum[tmp]-sum[i-1])*(n div i)*(m div i);
     i:=tmp+1;
   end;
  exit(ans);
end;

procedure init;
var i:longint;
begin
  prepare;
  read(n);
  for i:=1 to n do
   begin
     read(a,b,c,d,k);
     a:=(a-1)div k;
     b:=b div k;
     c:=(c-1)div k;
     d:=d div k;
     ans:=int64(calc(b,d))+int64(calc(a,c))-int64(calc(b,c))-int64(calc(a,d));
     writeln(ans);
   end;
end;

begin
  init;
end.

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

历史上的今天

评论

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

页脚

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