[反演 莫隊算法] HDU 4676 Sum Of Gcd

∑i=LR∑j=LRgcd(ai,aj)=∑i=LR∑j=LR∑d|ai,d|ajϕ(d)=∑dϕ(d)(∑i=LR[d|ai])2

這個東西現在想不到什麼好的方法維護 就暴力跑莫隊吧

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#define cl(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;

inline char nc(){
  static char buf[],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,,,stdin); if (p1==p2) return EOF; }
  return *p1++;
}

inline void read(int &x){
  char c=nc(),b=;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-;
  for (x=;c>='0' && c<='9';x=x*+c-'0',c=nc()); x*=b;
}

const int N=;

int phi[N];
vector<int> fac[N];
inline void Pre(int n=){
  phi[]=;
  int i,j;
  for (int i=;i<=n;i++)
    if(!phi[i])
      for (j=i;j<n;j+=i){
    if (!phi[j]) phi[j]=j;
    phi[j]-=phi[j]/i;
      }
  for (int i=;i<=n;i++)
    for (int j=i;j<=n;j+=i)
      fac[j].push_back(i);
}

int n,a[N];
int pos[N];
struct event{
  int l,r,idx;
  bool operator < (const event &B)const{ return pos[l]==pos[B.l]?r<B.r:pos[l]<pos[B.l]; }
}eve[N];
int tot;ll ans[N];

int num[N];
ll cur;

inline void add(int t){
  for (int i=;i<(int)fac[t].size();i++){
    int x=fac[t][i];
    cur+=(ll)num[x]*phi[x]; num[x]++;
  }
}
inline void del(int t){
  for (int i=;i<(int)fac[t].size();i++){
    int x=fac[t][i];
    num[x]--; cur-=(ll)num[x]*phi[x];
  }
}


int main(){
  int T,Case=;
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  read(T); Pre();
  while (T--){
    printf("Case #%d:\n",++Case);
    read(n); for (int i=;i<=n;i++) read(a[i]);
    read(tot); for (int i=;i<=tot;i++) read(eve[i].l),read(eve[i].r),eve[i].idx=i;
    int B=sqrt((double)n)+;
    for (int i=;i<=n;i++) pos[i]=(i-)/B+;
    sort(eve+,eve+tot+);

    int l=,r=; 
    for (int i=;i<=tot;i++){
      while (r<eve[i].r) add(a[++r]);
      while (r>eve[i].r) del(a[r--]);
      while (l<eve[i].l) del(a[l++]);
      while (l>eve[i].l) add(a[--l]);
      ans[eve[i].idx]=cur;
    }

    for (int i=;i<=tot;i++)
      printf("%I64d\n",ans[i]);
    cl(num); cur=;
  }
  return ;
}