题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=5869

题目：

给定序列和要查询的区间[L,R]，求[L,R]内有多少个不同的区间gcd

 

解题思路：

（1）遍历序列，预处理出以a[i]为结尾的区间的gcd并记录，注意，有多个以a[i]为结尾的区间gcd相同，取左边界最大的那个，这样在用线段树求不同区间gcd的数目时，就避免了-1和+1的更新，节省时间和空间。为了取左边界最大的那个，可以倒序处理，即依次求[i,i] [i-1,i] [i-2,i]...[1,i]的区间gcd，如果当前求的gcd和上次求的gcd相同，则不更新这个gcd对应的左边界。

尝试自己写代码遇到的问题：不能用map<int,int> gd[maxn]，因为map自动按照key值从小到大排序，影响结果，可以用pair和vector。此外，也不能用map中的key来存【x,i】的左边界x，如果这样的话在预处理时实践复杂度就达到了（n+1）*n/2, 会超时。

正确的处理方法：

vector<pair<int, int> > gd[maxn];//gd[i]中记录的是以a[i]为末尾的所有的gcd，<key,value>，表示【value，i】的区间gcd为key
void getIntervalGcd()
{
    for(int i = 1; i <= n; i++)
    {
        int x = a[i], y = i;
        gd[i].push_back(make_pair(x, y));
        for(int j = 0; j < gd[i-1].size(); j++)
        {
            int tmp = Gcd(gd[i-1][j].first, a[i]);
            if(tmp != x)
            {
                x = tmp, y = gd[i-1][j].second;
                gd[i].push_back(make_pair(x, y));
            }
        }
    }
}

补充一点：参照HDU5726 的第一种解题方法，可以求出序列中所有区间的gcd,但这个记录方法在本题中会MLE，并不适用

map<int, int> gc[maxn];//gc[i]中存放的（key，value）表示【key，i】的区间gcd为value
void getIntervalGcd()
{
    gc[1][1] = a[1];
    for(int i = 2; i  <= n; i++)
    {
        gc[i][i] = a[i];
        for(auto it = gc[i-1].begin(); it != gc[i-1].end(); it++)
        {
            int tmp = Gcd(it->second, a[i]);
            gc[i][it->first] = tmp;
        }
    }
}

（2）参考洛谷P1972的思路，求区间内不同的gcd数目

 

ac代码：

#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define lowbit(x) ((x) & (-x))
int n, q;
int c[maxn],a[maxn],ans[maxn];
vector<pair<int, int> > gd[maxn];//gd[i]中记录的是以a[i]为末尾的所有的gcd，<key,value>，表示【value，i】的区间gcd为key
map<int,int> last;
struct node {
    int l,r,no;
    friend bool operator < (node a, node b)
    {
        return a.r == b.r ? a.l < b.l : a.r < b.r;
    }
}ask[maxn];
int Gcd(int a, int b)
{
    return b == 0 ? a : Gcd(b, a % b);
}
void update(int x,int v)
{
    for(int i = x; i <= n; i += lowbit(i))
        c[i] += v;
}
int query(int x)
{
    int sum=0;
    for(int i = x; i > 0; i -= lowbit(i))
        sum += c[i];
    return sum;
}
void getIntervalGcd()
{
    for(int i = 1; i <= n; i++)
    {
        int x = a[i], y = i;
        for(int j = 0; j < gd[i-1].size(); j++)
        {
            int tmp = Gcd(gd[i-1][j].first, a[i]);
            if(tmp != x)
            {
                gd[i].push_back(make_pair(x, y));
                x = tmp, y = gd[i-1][j].second;
            }
        }
        gd[i].push_back(make_pair(x, y));
    }
}
void init()
{
    last.clear();
    for(int i = 1; i <= n; i++)
        gd[i].clear();
    memset(c, 0, sizeof(c));
}
int main()
{

    //freopen("/Users/zhangkanqi/Desktop/11.txt", "r", stdin);
    while(~scanf("%d %d",&n, &q))
    {
        init();
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        getIntervalGcd();
        for(int i = 1; i <= q; i++)
        {
            scanf("%d %d", &ask[i].l, &ask[i].r);
            ask[i].no = i;
        }
        sort(ask + 1, ask + 1 + q);
        int k = 1;//ask的下标从1开始
        for(int i = 1; i <= n; i++)
        {
            for(auto it = gd[i].begin(); it != gd[i].end(); it++)
            {
                int gcdValue=it->first, pos=it->second;
                if(last[gcdValue])//这个gcd的值之前访问过
                    update(last[gcdValue], -1);
                update(pos, 1);
                last[gcdValue] = pos;
            }
            while(ask[k].r == i)
            {
                ans[ask[k].no] = query(ask[k].r) - query(ask[k].l - 1);
                k++;
            }
        }
        for(int i = 1; i <= q; i++)
            printf("%d\n", ans[i]);
    }
    return 0;
}

 

【参考博客】：

https://www.cnblogs.com/shimu/p/5869810.html