首页 > 代码库 > Sum Of Gcd(hdu 4676)
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 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
153 2 5 4 131 52 43 3
Sample Output
Case #1:1140
思路：莫比乌兹反演+莫队；
然后后面的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\n",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:\n",__ca);119 for(i = 0; i < m; i++)120 printf("%lld\n",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 }
Sum Of Gcd(hdu 4676)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。