题目链接：
GCD
Time Limit: 10000/5000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description
Give you a sequence of N(N≤100,000) integers : a1,...,an(0<ai≤1000,000,000). There are Q(Q≤100,000) queries. For each query l,r you have to calculate gcd(al,,al+1,...,ar) and count the number of pairs(l′,r′)(1≤l<r≤N)such that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).
Input
The first line of input contains a number T, which stands for the number of test cases you need to solve.
The first line of each case contains a number N, denoting the number of integers.
The second line contains N integers, a1,...,an(0<ai≤1000,000,000).
The third line contains a number Q, denoting the number of queries.
For the next Q lines, i-th line contains two number , stand for the li,ri, stand for the i-th queries.
The first line of each case contains a number N, denoting the number of integers.
The second line contains N integers, a1,...,an(0<ai≤1000,000,000).
The third line contains a number Q, denoting the number of queries.
For the next Q lines, i-th line contains two number , stand for the li,ri, stand for the i-th queries.
Output
For each case, you need to output “Case #:t” at the beginning.(with quotes, t means the number of the test case, begin from 1).
For each query, you need to output the two numbers in a line. The first number stands for gcd(al,al+1,...,ar) and the second number stands for the number of pairs(l′,r′) such that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).
For each query, you need to output the two numbers in a line. The first number stands for gcd(al,al+1,...,ar) and the second number stands for the number of pairs(l′,r′) such that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).
Sample Input
1
5
1 2 4 6 7
4
1 5
2 4
3 4
4 4
Sample Output
Case #1:
1 8
2 4
2 4
6 1
题意：
给含有n个数的序列,现在询问[l,r]的gcd是多少,同时还要求与gcd相同的区间有多少个;
思路:
静态区间可以用rmq,先预处理就可以O(1)的回答询问了;还有就是询问区间的个数,可以先预处理出所有的gcd,用map存下来,预处理的时候枚举左端点,由于gcd是单调递减的,所以可以分层后二分右端点,找到每层的长度,加到map中,由于一个数的因子个数不超过log(n)所以层数比较少才可以这样处理,写的线段树t了,看来静态区间查询还是rmq好;
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
using namespace std;
#define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef long long LL;
template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
if(!p) { puts("0"); return; }
while(p) stk[++ tp] = p%10, p/=10;
while(tp) putchar(stk[tp--] + '0');
putchar('
');
}
const LL mod=1e9+7;
const double PI=acos(-1.0);
const int inf=1e9;
const int N=1e5+10;
const int maxn=500+10;
const double eps=1e-10;
int a[N],n,d[N][20];
map<int,LL>mp;
int gcd(int x,int y)
{
if(y==0)return x;
return gcd(y,x%y);
}
inline void rmq()
{
for(int i=1;i<=n;i++)d[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
d[i][j]=gcd(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
}
return ;
}
inline int query(int l,int r)
{
int k=0;
while((1<<(k+1))<=r-l+1)k++;
return gcd(d[l][k],d[r-(1<<k)+1][k]);
}
inline void Init()
{
mp.clear();
For(i,1,n)
{
int pos=i;
while(pos<=n)
{
int le=query(i,pos);
int l=pos,r=n;
while(l<=r)
{
int mid=(l+r)>>1;
if(query(i,mid)<le)r=mid-1;
else l=mid+1;
}
mp[le]+=(LL)(r-pos+1);
pos=r+1;
}
}
}
int main()
{
int t,Case=0;
read(t);
while(t--)
{
printf("Case #%d:
",++Case);
read(n);
For(i,1,n)read(a[i]);
rmq();
Init();
int q;
read(q);
int l,r;
while(q--)
{
read(l);read(r);
int ans=query(l,r);
printf("%d ",ans);
print(mp[ans]);
}
}
return 0;
}