求 [a,b] 中 与n 互素的数字个数
#include <iostream> #include <algorithm> using namespace std; const int N =200; #define int long long int tot,fac[N]; int hh,q[10005]; void getFac(int x){ tot=0; for(int i=2;i*i<=x;i++){ if(x%i==0){ fac[tot++]=i; while(x%i==0) x/=i; } } if(x>1) fac[tot++]=x; } int sov(int x){ hh=0; q[hh++]=-1; for(int i=0;i<tot;i++){ int t=hh; for(int j=0;j<t;j++) q[hh++]=-1*fac[i]*q[j]; } int s=0; for(int i=1;i<hh;i++) s+=x/q[i]; return s; } signed main(){ int tes,cas=0;cin>>tes; while(tes--){ int a,b,n; scanf("%lld%lld%lld",&a,&b,&n); getFac(n); printf("Case #%lld: %lld\n",++cas,b-sov(b)-(a-1-sov(a-1))); } }
标签:int,tot,++,hh,sov,hdu4135,lld From: https://www.cnblogs.com/towboa/p/17067759.html