[HDU] 4135 Co-prime

http://acm.hdu.edu.cn/showproblem.php?pid=4135

题意，求[A,B]内与n互质的数个数。

容斥原理，转化为求不互质的数个数，简单求。

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

typedef long long ll;

inline ll rd(){
  ll ret=0,f=1;char c;
  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
  while(isdigit(c))ret=ret*10ll+c-'0',c=getchar();
  return ret*f;
}

const int MAXN=1024;

ll A,B,n;
int cnt[1024*1024+1];
int prime[MAXN],tot;
ll val[MAXN][2];

void init(){tot=0;}

ll calc(ll x){
  int up=1<<tot;
  ll ret=0;
  for(int i=0;i<up;i++){
    ll tmp=1;
    for(int j=1;j<=tot;j++){
      if(i&(1<<(j-1))) tmp*=1ll*prime[j];
    }
    if(cnt[i]&1) ret+=x/tmp;
    else ret-=x/tmp;
  }
  return n-ret;
}

void solve(){
  A=rd();B=rd();n=rd();
  init();
  int up=sqrt(n),sav=n;
  for(int i=2;i<=up;i++){
    if(sav%i==0){
      prime[++tot]=i;
      while(sav%i==0) sav/=i;
    }
  }
  if(sav>1) prime[++tot]=sav;
  printf("%lld
",calc(B)-calc(A-1));
}

int main(){
  int T;
  T=rd();
  for(int i=1;i<=1024*1024;i++) cnt[i]=cnt[i>>1]+(i&1);
  for(int i=1;i<=T;i++) printf("Case #%d: ",i),solve();
  return 0;
}