任意门：http://acm.hdu.edu.cn/showproblem.php?pid=4676
Sum Of Gcd
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 908 Accepted Submission(s): 438
Problem Description
Given you a sequence of number a1, a2, ..., an, which is a permutation of 1...n.
You need to answer some queries, each with the following format:
Give you two numbers L, R, you should calculate sum of gcd(a[i], a[j]) for every L <= i < j <= R.
You need to answer some queries, each with the following format:
Give you two numbers L, R, you should calculate sum of gcd(a[i], a[j]) for every L <= i < j <= R.
Input
First line contains a number T(T <= 10),denote the number of test cases.
Then follow T test cases.
For each test cases,the first line contains a number n(1<=n<= 20000).
The second line contains n number a1,a2,...,an.
The third line contains a number Q(1<=Q<=20000) denoting the number of queries.
Then Q lines follows,each lines contains two integer L,R(1<=L<=R<=n),denote a query.
Then follow T test cases.
For each test cases,the first line contains a number n(1<=n<= 20000).
The second line contains n number a1,a2,...,an.
The third line contains a number Q(1<=Q<=20000) denoting the number of queries.
Then Q lines follows,each lines contains two integer L,R(1<=L<=R<=n),denote a query.
Output
For each case, first you should print "Case #x:", where x indicates the case number between 1 and T.
Then for each query print the answer in one line.
Then for each query print the answer in one line.
Sample Input
1
5
3 2 5 4 1
3
1 5
2 4
3 3
Sample Output
Case #1:
11
4
Source
题意概括：
给出 1~N 的一个排列，M次查询，每次查询 L ~ R 内 GCD( ai, aj ) [ L <= i < j <= R ] 的总和。
解题思路：
又是涉及 GCD 又是 涉及区间查询，头有点大。
首先莫队处理区间查询，其次欧拉函数解决GCD问题。
根据：
那么用 gcd( ai, aj) 代替上式的 n，我们可以得到：
问题就转换成了求 d 的欧拉函数，其实 d 是有很多重复的，那么我们只要统计出当前查询区间【L，R】内 d 出现的次数然后乘上其欧拉函数值，所求的的答案就是区间GCD的总和。
欧拉函数值和对原序列的每一项的因数分解预处理时搞定。
AC code：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std; const int MAXN = 2e4+;
int unit, a[MAXN], N, M, cnt[MAXN];
LL ans[MAXN], phi[MAXN];
vector<int>factor[MAXN]; struct Query
{
int l, r, idx;
friend bool operator < (const Query & a, const Query & b){
int x1 = a.l/unit, x2 = b.l/unit;
if(x1 != x2) return x1 < x2;
return a.r < b.r;
}
}Q[MAXN]; void init()
{
for(int i = ; i < MAXN; i++){ //分解因子
for(int j = i; j < MAXN; j+=i)
factor[j].push_back(i);
} phi[] = ; //欧拉函数
for(int i = ; i < MAXN; i++){
phi[i] = 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-);
}
//puts("zjy");
}
} LL add(int x)
{
LL res = ;
for(auto d : factor[x]) res+=cnt[d]*phi[d];
for(auto d : factor[x]) cnt[d]++;
return res;
} LL del(int x)
{
LL res = ;
for(auto d : factor[x]) cnt[d]--;
for(auto d : factor[x]) res+=cnt[d]*phi[d];
return -res;
} void solve()
{
memset(cnt, , sizeof(cnt));
int L = , R = ;
LL cur = ;
for(int i = ; i <= M; i++){
while( L < Q[i].l) cur += del(a[L++]);
while( L > Q[i].l) cur += add(a[--L]);
while( R < Q[i].r) cur += add(a[++R]);
while( R > Q[i].r) cur += del(a[R--]);
ans[Q[i].idx] = cur;
//puts("zjy");
}
} int main()
{
int T_Case, Cas = ;
init();
//puts("zjy");
scanf("%d", &T_Case);
while(T_Case--){
scanf("%d", &N);
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].idx = i;
}
unit = sqrt(N);
sort(Q+, Q++M);
solve();
printf("Case #%d:\n", ++Cas);
for(int i = ; i <= M; i++) printf("%lld\n", ans[i]);
}
return ;
}