给n个数， m个询问， 每个询问给出[l, r]， 问你对于任意i， j。gcd（a[i], a[j]） L <= i < j <= R的和。
假设两个数的公约数有b1, b2, b2...bn， 那么这两个数的最大公约数就是phi[b1] + phi[b2] + phi[b3]...+phi[bn]。
知道这个就可以用莫队了， 具体看代码。
#include <bits/stdc++.h> using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = ;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
const int maxn = 2e4+;
vector <int> v[maxn];
struct node
{
int l, r, block, id;
}q[maxn];
bool cmp(const node& a, const node& b)
{
if(a.block == b.block)
return a.r < b.r;
return a.block < b.block;
}
int phi[maxn], cnt[maxn], a[maxn];
ll res, ans[maxn];
void add(int x)
{
for(int i = ; i < v[x].size(); i++) {
res += phi[v[x][i]]*(cnt[v[x][i]]++);
}
}
void sub(int x)
{
for(int i = ; i < v[x].size(); i++) {
res -= phi[v[x][i]]*(--cnt[v[x][i]]);
}
}
void solve(int m)
{
int L = , R = ;
res = ;
mem(cnt);
for(int i = ; i < m; i++) {
while(R < q[i].r) {
add(a[++R]);
}
while(R > q[i].r) {
sub(a[R--]);
}
while(L < q[i].l) {
sub(a[L++]);
}
while(L > q[i].l) {
add(a[--L]);
}
ans[q[i].id] = res;
}
}
void init()
{
for(int i = ; i < maxn; i++) {
phi[i] = i;
for(int j = i; j < maxn; j += i) {
v[j].pb(i);
}
}
for(int i = ; i < maxn; i++) {
if(phi[i] == i) {
for(int j = i; j < maxn; j += i) {
phi[j] = phi[j]/i*(i-);
}
}
}
}
int main()
{
init();
int t, n, m;
cin>>t;
for(int casee = ; casee <= t; casee++) {
scanf("%d", &n);
int BLOCK = sqrt(n*1.0);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
}
scanf("%d", &m);
for(int i = ; i < m; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].block = q[i].l/BLOCK;
q[i].id = i;
}
sort(q, q+m, cmp);
solve(m);
printf("Case #%d:\n", casee);
for(int i = ; i < m; i++) {
printf("%lld\n", ans[i]);
}
}
}