hdu2841Visible Trees 容斥原理

hdu2841Visible Trees 容斥原理

//給定一個n*m的方格，農場主從(0 , 0 )開始看 ， 只能看到
//一條直線上的第一個格子，問農場主能看到幾個格子
//對於任意的坐標(x,y) ,與其在同一條直線上的坐標有(k*x , k*y)
//故而可以枚舉所有的x，找其在(1,m)有多少個互質的數
#include
#include
#include
#include
using namespace std ;
typedef __int64 ll ;
const int maxn = 100010 ;
int isp[maxn] ;
vector vec[maxn] ;
void set()
{
memset(isp , 0 , sizeof(isp)) ;
for(int i = 2;i < maxn;i+=2)
vec[i].push_back(2) ;
for(int i = 3;i < maxn;i+=2)
{
if(isp[i])continue ;
for(int j = i;j < maxn;j+=i)
{
isp[j] = 1;
vec[j].push_back(i) ;
}
}
}
int dfs(int pos , int x , int num)
{
int ans = 0 ;
for(int i = pos ;i < vec[x].size() ;i++)
ans += num/vec[x][i] - dfs(i+1 , x , num/vec[x][i]) ;
return ans ;
}
int main()
{
int n , m ;
set() ;
int T;scanf("%d" ,&T) ;
while(T--)
{
scanf("%d%d" , &n, &m) ;
ll ans = m;
for(int i = 2;i <= n;i++)
ans +=( m - dfs(0 , i , m)) ;
printf("%I64d\n" , ans) ;
}
return 0 ;
}