LightOJ 1370 Bi-shoe and Phi-shoe 欧拉函数+线段树

分析：对于每个数，找到欧拉函数值大于它的，且标号最小的，预处理欧拉函数，然后按值建线段树就可以了

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
const int N = 1e6+5;
const int INF=0x3f3f3f3f;
int phi[N],c[N<<2];
void pushup(int rt){
  c[rt]=min(c[rt<<1],c[rt<<1|1]);
}
void add(int rt,int l,int r,int pos,int t){
  if(l==r){
     c[rt]=min(c[rt],t);
     return;
  }
  int m=(l+r)>>1;
  if(pos<=m)add(rt<<1,l,m,pos,t);
  else add(rt<<1|1,m+1,r,pos,t);
  pushup(rt);
}
int get(int rt,int l,int r,int x,int y){
  if(x<=l&&r<=y)return c[rt];
  int m=(l+r)>>1;
  int ans=INF;
  if(x<=m)ans=min(ans,get(rt<<1,l,m,x,y));
  if(y>m)ans=min(ans,get(rt<<1|1,m+1,r,x,y));
  return ans;
}
int main(){
    phi[1]=1;
    for(int i=2;i<=N-2;++i){
      if(!phi[i]){
        for(int j=i;j<=N-2;j+=i){
          if(!phi[j])phi[j]=j;
          phi[j]=phi[j]/i*(i-1);
        }
      }
    }
    memset(c,INF,sizeof(c));
    for(int i=2;i<=N-2;++i)
      add(1,1,N-2,phi[i],i);
    int T,cas=0;
    scanf("%d",&T);
    while(T--){
       int n;
       scanf("%d",&n);
       LL ans=0;
       for(int i=1;i<=n;++i){
         int x;
         scanf("%d",&x);
         ans+=get(1,1,N-2,x,N-2);
       }
       printf("Case %d: %lld Xukha
",++cas,ans);
    }
    return 0;
}