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 (n \log^{3} n + q \log n))$

$O (T (n \log^{3} n + q \log n))$

var
  f:array[0..200010,0..20]of longint;
  a,h:array[0..980321]of int64;
  t,n,i,j,k,l,r,mid,num,cas:longint;

function log2(x:longint):longint;
begin
  exit(trunc(ln(x)/ln(2)));
end;

function exp(x:longint):longint;
begin
  exit(1<<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=0 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+1);
  exit(gcd(f[l,k],f[r-exp(k)+1,k]));
end;

function hash(x:int64):longint;
var
  k:longint;
begin
  k:=x mod 980321;
  while (h[k]<>0)and(h[k]<>x) do k:=(k+1) mod 980321;
  h[k]:=x;
  exit(k);
end;

procedure solve;
begin
  fillchar(a,sizeof(a),0);
  readln(n);
  for i:=1 to n do read(f[i][0]);
  for j:=1 to log2(n) do
  for i:=1 to n-exp(j)+1 do
  f[i][j]:=gcd(f[i][j-1],f[i+exp(j-1)][j-1]);
  for i:=1 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)>>1;
        if calc(i,mid+1)=k then l:=mid+1
        else r:=mid;
      end;
      inc(a[hash(k)],l-j+1);j:=l+1;
    end;
  end;
  readln(num);
  for i:=1 to num do
  begin
    readln(l,r);
    k:=calc(l,r);
    writeln(k,' ',a[hash(k)]);
  end;
end;

begin
  readln(t);
  while t>0 do
  begin
    dec(t);
    inc(cas);
    writeln('Case #',cas,':');
    solve;
  end;
end.

View Code