@ hdu 5726
ST表+gcd（）
数据大，不能暴力求，用线段树会超时，我们可以利用ST表求区间gcd；
至于第二问，对于以ai开头的区间来说，gcd随区间长度单调递减，藉此可在nlogn时间内利用二分求出每个gcd值出现次数，用map或hash存储即可
代码附下：
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #include<map> using namespace std; typedef long long ll;
ll logs[111111];
ll n,q,t;
ll x,y;
ll cnt;
ll f[111111][20]; inline ll gcd(ll a,ll b) {
return b==0?a:gcd(b,a%b);}
ll query(ll x,ll y) {
ll len=logs[y-x+1];return gcd(f[x][len],f[y-(1<<len)+1][len]); }
ll solve(ll a,ll tmp) {
ll ans=-1,ret=0,now;ll l=a,r=n;while(l<=r){
ll mid=(l+r)>>1;now=query(a,mid);if(now>tmp)l=mid+1;if(now<=tmp)r=mid-1;if(now==tmp)ans=mid;}if(ans!=-1)now=query(a,ans);else now=-1;while(now==tmp&&ans<=n){
ret++;ans++;now=query(a,ans);}return ret; } int main() {
for(ll i=1; i<=100000; ++i)logs[i]=log2(i)+1e-6;scanf("%lld",&t); for(ll u=1;u<=t;u++) {
scanf("%lld",&n,&q);for(ll i=1;i<=n;i++)scanf("%lld",&f[i][0]);for(ll i=1;i<17;i++)for(ll k=1;k<=n;k++){
if(k+(1<<i)-1>n) continue;f[k][i]=gcd(f[k][i-1],f[k+(1<<(i-1))][i-1]);}map<ll,ll> rec;for(ll i=1; i<=n; ++i){
ll g=f[i][0],j=i;while(j<=n){
ll l=j,r=n;while(l<r){
ll mid=l+r+1>>1;if(query(i,mid)==g) l=mid;else r=mid-1;}rec[g]+=(l-j+1);j=l+1;g=query(i,j);}}printf("Case #%d:\n",u);scanf("%lld",&q);for(ll i=1;i<=q;i++){
scanf("%lld%lld",&x,&y);cnt=0;ll tmp=query(x,y);printf("%lld %lld\n",tmp,rec[tmp]);} } return 0; }