学步园

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4676

解题思路：总体上这是一个数学题加上离线与分块处理加速。显然对于区间内有公约数x的数来说，假设有num[x]个x的倍数，那么答案显然是sigma(C(num[x],2)*f(x))，根据容斥原理f(x)应该是一个小于x的数并且满足sigma(f(d)) = x{d|x}，因为有x这个约数的数对一定也有d这个约数，其中d|x，所以我在加上C(num[x],2)*f(x)之前就把C(num[d],2)*f(d)加上了，而总共对于x所需累加的次数是x，所以有sigma(f(d))
= x{d|x}，而这正是麦比乌斯反演公式，可得f(d)为欧拉函数，http://www.isnowfy.com/mobius-inversion/

       然后每加入一个数我们只要加上num[x]*phi[x]就行了(根据组合公式的性质比较容易看出)。但是直接暴力的话复杂度会超，就是对于查询区间大幅波动的情况就需要不停的加入点，删除点，复杂度估计能达到n平方，所以我们采用离线查询的方式，然后对查询左端点分段排，在每一段内保证查询右端点的有序性，这样就可以大致保持查询左端点和右端点的有序性。下面上代码：

#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
#define N 20005
using namespace std;
int phi[N],a[N],num[N],ans[N];
int L,R,ret;
vector<int>d[N];
struct node
{
    int l,r,id,s;
}seg[N];
void init()
{
    for(int i = 1;i<N;i++)phi[i] = i;
    for(int i = 2;i<N;i++)
        if(phi[i] == i)
            for(int j = i;j<N;j+=i)
                phi[j] = phi[j]/i*(i-1);
    for(int i = 1;i<N;i++)
        for(int j = i;j<N;j+=i)
            d[j].push_back(i);
}
void Insert(int x)
{
    for(int i = 0;i<d[x].size();i++)
    {
        int v = d[x][i];
        ret+=num[v]*phi[v];
        num[v]++;
    }
}
void Delete(int x)
{
    for(int i = 0;i<d[x].size();i++)
    {
        int v = d[x][i];
        num[v]--;
        ret-=num[v]*phi[v];
    }
}
void query(int l,int r)
{
    for(int i = l;i<L;i++)Insert(a[i]);
    for(int i = L;i<l;i++)Delete(a[i]);
    for(int i = r+1;i<=R;i++)Delete(a[i]);
    for(int i = R+1;i<=r;i++)Insert(a[i]);
}
bool cmp(node x,node y)
{
    if(x.s == y.s)return x.r<y.r;
    return x.s<y.s;
}
int main()
{
    int t,y,n,m,i,j,cas = 1;
    scanf("%d",&t);
    init();
    while(t--)
    {
        scanf("%d",&n);
        int size = sqrt(1.0*n);
        memset(num,0,sizeof(num));
        for(i = 1;i<=n;i++)
            scanf("%d",&a[i]);
        scanf("%d",&m);
        for(i = 1;i<=m;i++)
        {
            scanf("%d%d",&seg[i].l,&seg[i].r);
            seg[i].id = i;
            seg[i].s = seg[i].l/size;
        }
        sort(seg+1,seg+m+1,cmp);
        ret = 0;
        L = seg[1].l;
        R = seg[1].r;
        for(i = L;i<=R;i++)Insert(a[i]);
        ans[seg[1].id] = ret;
        for(i = 2;i<=m;i++)
        {
            query(seg[i].l,seg[i].r);
            L = seg[i].l;
            R = seg[i].r;
            ans[seg[i].id] = ret;
        }
        printf("Case #%d:\n",cas++);
        for(i=1;i<=m;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}