hdu 4676 Sum Of Gcd

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<algorithm>
  4 #include<iomanip>
  5 #include<cmath>
  6 #include<cstring>
  7 #include<vector>
  8 #define ll __int64
  9 #define pi acos(-1.0)
 10 #define MAX 20002
 11 using namespace std;
 12 int R,L,an[MAX],euler[MAX],ans[MAX],res,num[MAX];
 13 bool vis[MAX],prime[MAX];
 14 struct node
 15 {
 16     int x,y,l,p;
 17 }q[MAX];
 18 vector<int>p[MAX];
 19 void init()//初始化欧拉函数值
 20 {
 21     int i,j;
 22     for(i=1;i<MAX;i++) euler[i]=i;
 23     for(i=2;i<MAX;i++)
 24     if(euler[i]==i){
 25         for(j=i;j<MAX;j+=i)
 26             euler[j]=euler[j]/i*(i-1);
 27     }
 28 }
 29 void factor(int n)//分解因子
 30 {
 31     p[n].clear();
 32     for(int i=1;i*i<=n;i++){
 33         if(n%i==0){
 34             p[n].push_back(i);
 35             if(i*i!=n) p[n].push_back(n/i);
 36         }
 37     }
 38 }
 39 bool cmp(const node &a,const node &b)
 40 {
 41     if(a.l==b.l) return a.y<b.y;
 42     return a.l<b.l;
 43 }
 44 void query(int x,int y,int flag)//查询操作
 45 {
 46     int t;
 47     if(flag){
 48         for(int i=x;i<L;i++){
 49             for(int j=0;j<p[an[i]].size();j++){
 50                 t=p[an[i]][j];
 51                 res+=num[t]*euler[t];
 52                 num[t]++;
 53             }
 54         }
 55         for(int i=L;i<x;i++){
 56             for(int j=0;j<p[an[i]].size();j++){
 57                 t=p[an[i]][j];
 58                 num[t]--;
 59                 res-=num[t]*euler[t];
 60             }
 61         }
 62         for(int i=y+1;i<=R;i++){
 63             for(int j=0;j<p[an[i]].size();j++){
 64                 t=p[an[i]][j];
 65                 num[t]--;
 66                 res-=num[t]*euler[t];
 67             }
 68         }
 69         for(int i=R+1;i<=y;i++){
 70             for(int j=0;j<p[an[i]].size();j++){
 71                 t=p[an[i]][j];
 72                 res+=num[t]*euler[t];
 73                 num[t]++;
 74             }
 75         }
 76     }
 77     else{
 78         for(int i=x;i<=y;i++){
 79             for(int j=0;j<p[an[i]].size();j++){
 80                 t=p[an[i]][j];
 81                 res+=num[t]*euler[t];
 82                 num[t]++;
 83             }
 84         }
 85     }
 86     L=x;R=y;
 87 }
 88 int main(){
 89     int n,t,i,j,m,c,ca=0;
 90     init();
 91     for(i=1;i<=20000;i++) factor(i);
 92     scanf("%d",&c);
 93     while(c--){
 94         scanf("%d",&n);
 95         for(i=1;i<=n;i++) scanf("%d",&an[i]);
 96         m=sqrt(1.0*n);
 97         scanf("%d",&t);
 98         for(i=0;i<t;i++){
 99             scanf("%d%d",&q[i].x,&q[i].y);
100             q[i].l=q[i].x/m;
101             q[i].p=i;
102         }
103         sort(q,q+t,cmp);
104         res=0;
105         memset(num,0,sizeof(num));
106         for(i=0;i<t;i++){
107             query(q[i].x,q[i].y,i);
108             ans[q[i].p]=res;
109         }
110         printf("Case #%d:
",++ca);
111         for(i=0;i<t;i++)
112             printf("%d
",ans[i]);
113     }
114     return 0;
115 }