Problem Description

Given you a sequence of number a₁, a₂, ..., a_n, 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.

 

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 a₁,a₂,...,a_n.
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.

 

Sample Input

 

Sample Output

 

Source

 #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 ;

 }