程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2841-Visible Trees（容斥原理）

HDU 2841-Visible Trees（容斥原理）

編輯：C++入門知識

HDU 2841-Visible Trees（容斥原理）

題目鏈接：傳送門

題意：有一個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;
}