hdu 2841 Visible Trees(容斥原理) - c++编程基础

有一个n*m的方格，从(1,1)开始，每个点有一棵树，一个人站在(0,0)点，问他能看到几棵树。当(0,0)和另外的点在一条直线上时他只能看到最近的一棵。

题目意在求在m*n的方格中有多少种y/x，因为两个y/x相等的点只能看到一个。有多少种y/x也就是有多少个（x,y）x与y互质。其中(1<=x<=m,1<=n<=y)。

这样就上一题类似了，求一个区间[1,m]内与i的互质的数的个数。这里1<=i<=n，先求出与i不互质的，对i分解质因子然后容斥。

#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 ans; int n,m; 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(int 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(%d %d,&n,&m); if(n > m) swap(n,m); ans = 0; for(int i = 1; i <= n; i++) { getFac(i); ans += solve(m); } printf(%I64d ,ans); } return 0; }