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

 

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

 

#include
     
      #include
      
       #include
       
        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<
        
         1) prime[++tot]=sav;  printf("%lld\n",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;}