hdu1695(莫比乌斯)或欧拉函数+容斥 - c++编程基础

题意：求1-b和1-d之内各选一个数组成数对，问最大公约数为k的数对有多少个，数对是有序的。(b,d,k<=100000)

解法1：这个可以简化成1-b/k 和1-d/k 的互质有序数对的个数。假设b=b/k，d=d/k,b<=d.欧拉函数可以算出1-b与1-b之内的互质对数，然后在b+1到d的数i，求每个i在1-b之间有多少互质的数。解法是容斥，getans函数参数的意义：1-tool中含有rem位置之后的i的质因子的数的个数。

在

for(int j=rem;j<=factor[i][0];j++)
    ans+=tool/factor[i][j]-getnum(i,tool/factor[i][j],j+1);

这个循环中，ans加的等号后每项表示当前最大的质因子是factor[i][j]的数量，目的是去重。

解法2：莫比乌斯，莫比乌斯数组确实很有用。其实也很简单，mou的位置的含义是，首先如果i有个质因子出现2次或以上，则mou值为0，否则1与-1跟i的质因子奇偶性决定。目的也是容斥。

解法1代码：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=100010; const LL INF=0x3FFFFFFF; int a, b, c, d, k; int factor[Max][20]; bool rem[Max]; LL oular[Max]; void init() { for(int i=1; i
              
               >t; init();int kk=1; while(t--) { cin>>a>>b>>c>>d>>k; printf("Case %d: ",kk++); if(k==0) { cout<<"0\n"; continue; } b/=k; d/=k; if(b>d)swap(b,d); LL ans=oular[b]; for(int i=b+1;i<=d;i++) { ans+=b-getnum(i,b,1); } cout<
               
                解法2代码：
                /******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
                 
                  
#include 
                  
                    #include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         #include 
                        
                          #include 
                          #include 
                          
                            #include 
                           
                             #include 
                            
                              //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=100010; const LL INF=0x3FFFFFFF; int a, b, c, d, k; bool rem[Max]; int mou[Max]; void init() { mou[1]=1; for(LL i=2; i
                             
                              >t; init(); int kk=1; while(t--) { cin>>a>>b>>c>>d>>k; printf("Case %d: ",kk++); if(k==0) { cout<<"0\n"; continue; } b/=k; d/=k; if(b > d)swap(b,d); long long ans1 = 0; for(int i = 1; i <= b; i++) ans1 += (long long)mou[i]*(b/i)*(d/i); long long ans2 = 0; for(int i = 1; i <= b; i++) ans2 += (long long)mou[i]*(b/i)*(b/i); ans1 -= ans2/2; cout<