暑假颓废了好久啊。。。重新开始写博客
题目大意：给定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.