Sum Of Gcd(hdu 4676)

Sum Of Gcd

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 738 Accepted Submission(s): 333

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

1 5 3 2 5 4 1 3 1 5 2 4 3 3

Sample Output

Case #1: 11 4 0

思路：莫比乌兹反演+莫队；

然后后面的s（d）就是欧拉函数；

以上参考http://www.ithao123.cn/content-4754688.html；

然后用莫队算法维护下；

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<queue>
  7 #include<vector>
  8 #include<stack>
  9 #include<set>
 10 using namespace std;
 11 typedef long long LL;
 12 int ans[100000];
 13 int mul[100000];
 14 typedef struct node
 15 {
 16     int l;
 17     int r;
 18     int id;
 19 } ss;
 20 ss ask[100000];
 21 bool cmp1(node p,node q)
 22 {
 23     return p.l < q.l;
 24 }
 25 bool cmp2(node p,node q)
 26 {
 27     return p.r < q.r;
 28 }
 29 bool prime[30000];
 30 int prime_table[30000];
 31 vector<int>vec[30000];
 32 int cnt[20005];
 33 LL answ[30000];
 34 int oula[20005];
 35 void _slove_mo(int n,int m);
 36 int main(void)
 37 {
 38     int n,m;
 39     int T;
 40     int __ca = 0;
 41     int cn = 0;
 42     mul[1] = 1;
 43     int i,j;
 44     memset(prime,0,sizeof(prime));
 45     for(i = 0; i <= 20000; i++)
 46         oula[i] = i;
 47     for(i = 2; i <= 20000; i++)
 48     {
 49         if(!prime[i])
 50         {
 51             prime_table[cn++] = i;
 52             mul[i] = -1;
 53         }
 54         for(j = 0; j < cn&&(i*prime_table[j]<=20000); j++)
 55         {
 56             if(i%prime_table[j])
 57             {
 58                 prime[i*prime_table[j]] = true;
 59                 mul[i*prime_table[j]] = -mul[i];
 60             }
 61             else
 62             {
 63                 prime[i*prime_table[j]] = true;
 64                 mul[i*prime_table[j]] = 0;
 65                 break;
 66             }
 67         }
 68     }//printf("%d
",cn);
 69     for(i = 0; i < cn; i++)
 70     {
 71         for(j = 1; j*prime_table[i]<=20000; j++)
 72         {
 73             oula[j*prime_table[i]]/=prime_table[i];
 74             oula[j*prime_table[i]]*=(prime_table[i]-1);
 75         }
 76     }
 77     for(i = 1; i <= 20000; i++)
 78     {
 79         for(j = 1; j <= sqrt(i); j++)
 80         {
 81             if(i%j==0)
 82             {
 83                 vec[i].push_back(j);
 84                 if(i/j != j)
 85                     vec[i].push_back(i/j);
 86             }
 87         }
 88     }scanf("%d",&T);
 89     while(T--)
 90     {
 91         ++__ca; memset(cnt,0,sizeof(cnt));
 92         scanf("%d",&n);
 93         for(i = 1; i <= n; i++)
 94         {
 95             scanf("%d",&ans[i]);
 96         }
 97         scanf("%d",&m);
 98         for(i = 0; i < m; i++)
 99         {
100             scanf("%d %d",&ask[i].l,&ask[i].r);
101             ask[i].id = i;
102         }
103         sort(ask,ask+m,cmp1);
104         int id = 0;
105         int ak = sqrt(1.0*n)+1;
106         int v = ak;
107         for(i = 0; i < m; i++)
108         {
109             if(ask[i].l > v)
110             {
111                 v += ak;
112                 sort(ask+id,ask+i,cmp2);
113                 id = i;
114             }
115         }
116         sort(ask+id,ask+m,cmp2);
117         _slove_mo(n,m);
118         printf("Case #%d:
",__ca);
119         for(i = 0; i < m; i++)
120             printf("%lld
",answ[i]);
121 
122     }return 0;
123 }
124 void _slove_mo(int n,int m)
125 {
126     int i,j;
127     LL sum = 0;
128     int xl = ask[0].l;
129     int xr = ask[0].r;
130     for(i = xl; i <= xr; i++)
131     {
132         for(j = 0; j < vec[ans[i]].size(); j++)
133         {   int x = vec[ans[i]][j];
134             sum = sum + (LL)oula[x]*(LL)cnt[x];
135             cnt[x]++;
136         }
137     }
138     answ[ask[0].id] = sum;
139     for(i = 1; i < m; i++)
140     {
141         while(xl < ask[i].l)
142         {
143             int y = ans[xl];
144             for(j = 0; j < vec[y].size(); j++)
145             {
146                 int x = vec[y][j];
147                 sum -= (LL)oula[x]*(LL)(--cnt[x]);
148             }
149             xl++;
150         }
151         while(xl > ask[i].l)
152         {
153             xl--;
154             int y = ans[xl];
155             for(j = 0; j < vec[y].size(); j++)
156             {
157                 int x = vec[y][j];
158                 sum += (LL)oula[x]*(LL)(cnt[x]++);
159             }
160         }
161         while(xr > ask[i].r)
162         {
163             int y = ans[xr];
164             for(j = 0; j < vec[y].size(); j++)
165             {
166                 int x = vec[y][j];
167                 sum -= (LL)oula[x]*(LL)(--cnt[x]);
168             }
169             xr--;
170         }
171         while(xr < ask[i].r)
172         {
173             xr++;
174             int y = ans[xr];
175             for(j = 0; j < vec[y].size(); j++)
176             {
177                 int x = vec[y][j];
178                 sum += (LL)oula[x]*(LL)(cnt[x]++);
179             }
180         }
181         answ[ask[i].id] = sum;
182     }
183 }