SDUT 3023-当N遇上M（容斥原理） - c++编程基础

题目链接：传送门

题意：求[1,n]内与m互质的个数。

容斥原理：奇加偶减（奇数个类的计数和-偶数个类的计数和）

对于这个问题，首先求出m的质因数fac[] , 然后所在区间内有n/fac[i]个数一定不能与m互质（比如m=8，n=10，对于fac[]=2,有2,4,6,8,10 即5（10/2）个数不能与8互质）。。枚举每一个质因数选还是不选。可以位运算，也可以dfs

第一发容斥，准备系统的刷一下容斥的专题了。。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #define maxn 360 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1000000007 #define pp pair
               
                 #define ull unsigned long long #define max(x,y) ( ((x) > (y)) ? (x) : (y) ) #define min(x,y) ( ((x) > (y)) ? (y) : (x) ) using namespace std; ll fac[1111],tot,ans; void div(ll x)//分解质因数 { tot=0; for(ll i=2;i*i<=x;i++) { if(x&&x%i==0) { fac[tot++]=i; while(x&&x%i==0) x/=i; } } if(x>1) fac[tot++]=x; } void dfs(ll num,ll s,ll r,ll n)//n为范围 即（1,n） { if(num==tot) { if(s&1)ans-=n/r;//容斥原理：奇加偶减(那这里为什么还是减？因为n/r是不能和m互质的个数啦) else ans+=n/r; return ; } dfs(num+1,s,r,n); dfs(num+1,s+1,r*fac[num],n); } int main() { ll n,m; while(~scanf("%lld%lld",&n,&m)) { ans=0;div(m); dfs(0,0,1,n); printf("%lld\n",ans); } return 0; }