HDU 2841-Visible Trees（容斥原理） - c++编程基础

题目链接：传送门

题意：有一个n*m的矩阵上布满了树（矩阵从（1,1）开始），现在有一个农夫站在（0,0）点，问农夫可以看到多少棵树，其中如果这些树在一条线上那么只能看到最前面的那棵树，这个一开始看到确实蒙了。。看了题解其实是挺简单的。首先考虑只能看到一条线上最前面的那棵树这个条件，对于坐标比如（2,3）（4,6）（6,9）。。等这些坐标是在一条直线上的可以看出其除了（2,3）其他的都是由（2,3）的x坐标*k y坐标*k 得到的，拓展出来就是对于任意坐标（x，y）令a=x/gcd(x,y) b=y/gcd(x,y) 那么那些和(x,y) 在一条直线的点的坐标可以表示为 (x+(-)a*k,y+(-)b*k) ,显然(a,b) 是这条线上的第一个点，即农夫可以看到的点，所以总的问题就可以转换为求x∈（1，n）y∈（1，m）范围内满足 x，y互质的坐标的个数。枚举(1,n)内的x坐标 ,求x与（1，m）内互质的数个数。

#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[maxn],tot,n,m,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) { if(num==tot) { if(s&1)ans-=n/r; else ans+=n/r; return ; } dfs(num+1,s,r,n); dfs(num+1,s+1,r*fac[num],n); } void solve() { ans=0; for(ll i=1;i<=m;i++) { div(i); dfs(0,0,1,n); } printf("%I64d\n",ans); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%I64d%I64d",&m,&n); solve(); } return 0; }