2016多校联合训练1 D题GCD (ST表+二分)

暑假颓废了好久啊。。。重新开始写博客

题目大意：给定10w个数，10w个询问。每次询问一个区间[l,r]，求出gcd(a[l],a[l+1],...,a[r])以及有多少个区间[l',r']满足gcd(a[l'],a[l'+1],...,a[r'])==gcd(a[l],a[l+1],...,a[r])。

第一问就是简单的ST表了，f[i,j]表示i~i+2^j-1的gcd是多少，预处理出来就可以O(1)查询了。

第二问需要分析一下。首先，对于任意一个左端点，显然随着右端点的右移，这个区间的gcd是单调不升的。然后因为一个数的质因子的个数是logn，所以确定了左端点之后，无论右端点在哪，这个区间的gcd个数都不超过logn。于是我们就可以枚举左端点，每次二分找到一个新的gcd，把右端点变成这个新的gcd的位置，然后给上一个找到的gcd出现次数增加这个区间的点的个数，这里得用map存。（PS：pascal就用hash就行了）

总的时间复杂度O(T(nlog3n+Qlogn))。

代码如下：

var

  f:array[..,..]of longint;

  a,h:array[..]of int64;

  t,n,i,j,k,l,r,mid,num,cas:longint;

function log2(x:longint):longint;

begin

  exit(trunc(ln(x)/ln()));

end;

function exp(x:longint):longint;

begin

  exit(<<x);

end;

function max(a,b:longint):longint;

begin

  if a>b then exit(a);

  exit(b);

end;

function gcd(a,b:longint):longint;

begin

  if b= then exit(a)

  else exit(gcd(b,a mod b));

end;

function calc(l,r:longint):longint;

var

  k:longint;

begin

  k:=log2(r-l+);

  exit(gcd(f[l,k],f[r-exp(k)+,k]));

end;

function hash(x:int64):longint;

var

  k:longint;

begin

  k:=x mod ;

  while (h[k]<>)and(h[k]<>x) do k:=(k+) mod ;

  h[k]:=x;

  exit(k);

end;

procedure solve;

begin

  fillchar(a,sizeof(a),);

  readln(n);

  for i:= to n do read(f[i][]);

  for j:= to log2(n) do

  for i:= to n-exp(j)+ do

  f[i][j]:=gcd(f[i][j-],f[i+exp(j-)][j-]);

  for i:= to n do

  begin

    j:=i;

    while j<=n do

    begin

      k:=calc(i,j);l:=j;r:=n;

      while (l<r) do

      begin

        mid:=(l+r)>>;

        if calc(i,mid+)=k then l:=mid+

        else r:=mid;

      end;

      inc(a[hash(k)],l-j+);j:=l+;

    end;

  end;

  readln(num);

  for i:= to num do

  begin

    readln(l,r);

    k:=calc(l,r);

    writeln(k,' ',a[hash(k)]);

  end;

end;

begin

  readln(t);

  while t> do

  begin

    dec(t);

    inc(cas);

    writeln('Case #',cas,':');

    solve;

  end;

end.

巴特西

2016多校联合训练1 D题GCD (ST表+二分)

最新文章

热门文章