题目链接 : 点这里
题意：给了一个数列a，然后给了一个区间[L, R]，然后要求 sigma(gcd(i, j)), L <= i < j <= R。
解题方法： 令g(l, r) = sigma(gcd(i, j)), L <= i < j <= R.举个栗子，当a[L:R] = {4, 5, 8}时， 答案是1 + 1 + 4 = 6。由于最大公约数本身的定义，我们可以猜想多个数的gcd之和一定和这些数约数个数相关。比如4的约数1,2,4。5的约数为1,5。8的约数为1,2,4,8。=》 num[1] = 3, num[2] = 1, num[4] = 2, num[5] = 1, num[8] = 1。猜想答案为 g(l, r) = sigma(d * C(2, num(d)))， 其中C(a, b) 代表组合数。这里的d代表L,R区间里面所有数的约数。但是经过栗子计算会发现答案不正确，为什么？因为显然出现了重复计数，那么我们非常显然的想到了容斥。修正一下g(l, r) = sigma(f(d) * C(2, num(d)))。其中sigma(f(d)) = n, 其中n整除d。后面这个式子是怎么来的？？？对于一个已经统计过的数，那么它的约数一定被统计过，为了避免重复统计，那么对n所有约数统计的次数之和等于n，f其实就是欧拉函数，学过莫比乌斯反演就非常明白这里了。。。为了解决这个问题，今天下午看了一下午PO爷的莫比乌斯反演的论文2333。所以g(l, r) = sigma(phi(d)*C(2, num(d)))。
那么直接搞显然会t的对吧，那么想我们知道[l, r]的信息可以O(1)得到[l, r+1], [l, r - 1], [l - 1, r], [l + 1, r]的信息吗？？？显然可以啊。其实变化就是sigma(num[d] * phi(d))。自己画一下就明白了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 10;

int T, ks, n, m, block, a[maxn], cnt[maxn], pos[maxn];
long long ans[maxn], phi[maxn], Ans;
vector <int> factor[maxn];

struct Q{
    int l, r, id;
    Q(){}
    Q(int l, int r, int id) : l(l), r(r), id(id) {}
    bool operator < (const Q &rhs) const{
        if(pos[l] == pos[rhs.l]) return r < rhs.r;
        return pos[l] < pos[rhs.l];
    }
}q[maxn];

void pre_init(){
    for(int i = 1; i < maxn; i++)
        for(int j = i; j < maxn; j += i)
            factor[j].push_back(i);
    phi[1] = 1;
    for(int i = 2; i < maxn; i++){
        if(!phi[i]){
            for(int j = i; j < maxn; j += i){
                if(!phi[j]) phi[j] = j;
                phi[j] = phi[j] * (i - 1) / i;
            }
        }
    }
}

long long add(int x)
{
    long long res = 0;
    for(auto d : factor[x]) res += cnt[d] * phi[d];
    for(auto d : factor[x]) cnt[d]++;
    return res;
}

long long del(int x){
    long long res= 0;
    for(auto d : factor[x]) cnt[d]--;
    for(auto d : factor[x]) res += cnt[d] * phi[d];
    return -res;
}


int main(){
    pre_init();
    scanf("%d", &T); while(T--){
        scanf("%d", &n);
        block = sqrt(n);
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]), pos[i] = (i - 1) / block;
        scanf("%d", &m);
        for(int i = 1; i <= m; i++){scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i;}
        sort(q + 1, q + m + 1);
        int L = 1, R = 0;
        Ans = 0;
        for(int i = 1; i <= m; i++){
            int id = q[i].id;
            while(L < q[i].l) Ans += del(a[L]), L++;
            while(L > q[i].l) --L, Ans += add(a[L]);
            while(R < q[i].r) ++R, Ans += add(a[R]);
            while(R > q[i].r) Ans += del(a[R]), R--;
            ans[id] = Ans;
        }
        printf("Case #%d:\n", ++ks);
        for(int i = 1; i <= m; i++){
            printf("%lld\n", ans[i]);
        }
    }
    return 0;
}