题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2841
题目大意：
在平面(1,1)到(n,m)两点之间的矩形中一共有n×m棵树，求站在点(0,0)的人一共能看到多少棵没有被挡住的树？
分析：
如果一棵树的坐标为(x,y)，且g=gcd(x,y)=1 ，则(x′,y′)=(gx,gy)，说明(x,y)在点(0,0)到点(x′,y′)的线段延长线上，所以(x,y)会被挡住
那么只要枚举所有满足坐标(x,y)，gcd(x,y)=1的点即可，基本的容斥过程
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 100000+10;
vector<int> ft[120005];
bool isprime[120000];
void init()
{
for (int i = 2 ; i <= maxn ; i ++)
{
if (!isprime[i])
{
for (int j = i ; j <= maxn ; j += i)
{
isprime[j] = true;
ft[j].push_back(i);
}
}
}
}
ll solve(int x,int sta,ll n)
{
int pos = 0;
ll temp = 1;
while (sta)
{
if (sta&1)
temp *= ft[x][pos];
pos ++;
sta >>= 1;
}
return n/temp;
}
int m,n;
int main(){
init();
int T,t=1;
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&m,&n);
if (m>n)
swap(m,n);
ll ans = 0;
for (int i = 1 ; i <= n ; i ++)
{
ans += m;
for (int j = 1 ; j < (1<<ft[i].size()); j ++)
{
ll temp = solve(i,j,m);int cp = j,cnt = 0;
//printf("cp = %n\t",cp);
while (cp)
{
cp -= cp&(-cp);
cnt++;
}
//printf("cnt = %n\n",cnt);
if (cnt&1) ans -= temp;
else ans += temp;
}
//printf("%d\n",ans);
}
printf("%lld\n",ans);
}
return 0;
}
|