题目戳这里

题意：求一个区间[a,b]中有多少个与n互素的数。

思路：

这道题是容斥原理的模板题之一，容斥原理请参考容斥原理详述，很好的一篇文章。

[a,b]中与n互素的数目可转化为[1,b]-[1,a-1]的数目。

?

给出整数n和r。求区间[1;r]中与n互素的数的个数的方法：

解决它的逆问题，求不与n互素的数的个数。

考虑n的所有素因子pi(i=1…k)

在[1;r]中有多少数能被pi整除呢？它就是：

然而，如果我们单纯将所有结果相加，会得到错误答案。有些数可能被统计多次（被好几个素因子整除）。所以，我们要运用容斥原理来解决。

我们可以用o(2^k)的算法求出所有的pi组合，然后计算每种组合的pi乘积，通过容斥原理来对结果进行加减处理。

?

code：

?

/*
*Author : Flint_x 
*Created Time : 2015-07-20 13:22:56 
*File name : whust1_H.cpp 
*/

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
         
        
       
      
     
    
   
  

?