hdu 4135 Co-prime(容斥原理) - c++编程基础

求连续区间[a,b]内与n互质的数的个数。

因为a,b相当大，考虑用容斥原理。只需先求出[a,b]内与n不互质的数的个数，等于[1,b]内与n不互质的个数 - [1,a-1]内与n不互质的个数。问题转化为求【1，m】内与n不互质的数的个数。

先对n分解质因子，[1,m]内是n的质因子的倍数的那些数肯定与n不互质，但是有许多重复的，需要减去。质因子解法有多种，队列数组或状态压缩。

例如30的质因子是2,3,5，[1,m]内与30互质的数的个数表示为 n/2 + n/3 + n/5 - n/(2*3) - n/(2*5) - n/(3*5) + n/(2*3*5)。发现质因子个数是奇数的做加法，是偶数的做减法。队列数组解法为模拟一个队列，初始将1加入队列，之后每次取出n的一个质因子依次与队列中的数相乘后置于队尾，每次乘-1决定其前面的正负号。最后队列里的就是上式所有的分子，然后解之。状态压缩便是将取出的质因子置为1没取出的置为0，得到一个数res，若res的质因子个数是奇数就加上，是偶数就减，求和就是与m不互素的数的个数，解之。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #define LL __int64 //#define LL long long #define eps 1e-9 #define PI acos(-1.0) using namespace std; const LL INF = 1<<30; const int maxn = 100010; LL a,b,n; LL ans; int fac[maxn]; int prime[maxn]; int facCnt; void getPrime() { bool flag[maxn]; memset(flag,false,sizeof(flag)); prime[0] = 0; for(int i = 2; i < maxn; i++) { if(flag[i] == false) prime[++prime[0]] = i; for(int j = 1; j <= prime[0]&&i*prime[j]
                
                  1) fac[facCnt++] = tmp; } LL solve(LL m) { //位运算 LL anw = 0; for(int i = 1; i < (1<
                 
                  ?
                  ?
                  #include 
                   
                    
#include 
                    
                      #include
                      #include 
                      
                        #include 
                       
                         #include 
                        
                          #include 
                         
                           #include 
                          
                            #include 
                           
                             #include 
                            
                              #include 
                             
                               #include 
                              
                                #include 
                               
                                 #include 
                                
                                  #define LL __int64 //#define LL long long #define eps 1e-9 #define PI acos(-1.0) using namespace std; const LL INF = 1<<30; const int maxn = 100010; LL a,b,n; LL ans; int fac[maxn]; int prime[maxn]; int facCnt; void getPrime() { bool flag[maxn]; memset(flag,false,sizeof(flag)); prime[0] = 0; for(int i = 2; i < maxn; i++) { if(flag[i] == false) prime[++prime[0]] = i; for(int j = 1; j <= prime[0]&&i*prime[j]
                                 
                                   1) fac[facCnt++] = tmp; } LL solve(LL m) { //队列数组 int que[110]; int l = 0; que[l++] = 1; for(int i = 0; i < facCnt; i++) { int k = l; for(int j = 0; j < k; j++) que[l++] = fac[i]*que[j]*(-1); } LL anw = 0; for(int i = 0; i < l; i++) anw += m/que[i]; return anw; } int main() { int test; scanf(%d,&test); getPrime(); for(int item = 1; item <= test; item++) { scanf(%I64d %I64d %I64d,&a,&b,&n); getFac(); ans = solve(b) - solve(a-1); printf(Case #%d: %I64d ,item,ans); } return 0; } 
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                    
                    
                  
 
                  
 
                  ? 
                  ?