CC

自然万物都趋向从有序变得无序

0%

HDU-2841 Visible Trees（容斥原理）

发表于 更新于 分类于 Valine：

题目链接

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

There are many trees forming a m * n grid, the grid starts from (1,1). Farmer Sherlock is standing at (0,0) point. He wonders how many trees he can see. If two trees and Sherlock are in one line, Farmer Sherlock can only see the tree nearest to him.

Input

The first line contains one integer t, represents the number of test cases. Then there are multiple test cases. For each test case there is one line containing two integers m and n(1 ≤ m, n ≤ 100000)

Output

For each test case output one line represents the number of trees Farmer Sherlock can see.

Source

2009 Multi-University Training Contest 3 - Host by WHU

Sample Input

2
1 1
2 3

Sample Output

1
5

题意:

给一个n × m的矩阵，一个人站在(0,0)点，问它能看见多少点。

思路:

容斥

之前做过一个题和这个很像，那题是一个n×n的矩阵，那个题比较简单直接求欧拉函数就行了，

对于这个题，我们知道对于一个点，我们站在原点如果能看见它的话，那么之前没有任何点能挡住它，也就可以理解为在这之前没有和它共线的点，也就是说，对于斜率相同的点，我们只能计算一次，那么换句话说对于此题而言就是计算1！～n中的每个数在1～m中有多少个数与它互质。

对于计算1～m中有对个数于 i 互质，我们可以通过枚举i的因子来计算，枚举i的因子，计算m内有多少个数是因子的倍数，计算它对答案的贡献，这里就需要 容斥，因为比如说一个数6，在算2和3的时候分别计算了一次，那么就需要容斥来解决这种问题。

代码:

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
/*************************************************************************
    > File Name: HDU2841.cpp
    > Author: wood
    > Mail: cbcruel@gmail.com
    > Created Time: 2018年07月31日 星期二 15时52分30秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<string>

using namespace std;
typedef long long LL;
#define sqr(x) (x)*(x)
const double eps = 1e-8;
const double C = 0.57721566490153286060651209;
const double pi = acos(-1.0);
const LL mod = 1e9 + 7;
const int maxn = 1e5 + 10;

LL pri[maxn], fac[maxn];
bool vis[maxn];
int cnt;

void init(){
    cnt = 0;
    for(int i = 2; i < maxn; ++i){
        if(!vis[i]) pri[++cnt] = i;
        for(int j = 1; j <= cnt && i * pri[j] < maxn; ++ j){
            vis[i*pri[j]] == 1;
            if(i % pri[j] == 0) break;
        }
    }
}

int getf(int n){
    int t = 0;
    for(int i = 1; i <= cnt && pri[i] * pri[i] <= n; ++i){
        if(n % pri[i] == 0){
            fac[t++] = pri[i];
            while(n % pri[i] == 0) n /= pri[i];
        }
    }if(n > 1) fac[t++] = n;
    return t;
}

int main(){
    init();
    int t;
    scanf("%d", &t);
    while(t--){
        int n, m;
        scanf("%d %d", &n, &m);
        LL ans = m;
        for(int i = 2; i <= n; ++i){
            int t = getf(i);
            for(int j = 0; j < (1 << t); ++j){
                int s = 1;
                LL tmp = 1;
                for(int k = 0; k < t; ++k)
                if(j&(1<<k)){
                    s++;
                    tmp *= fac[k];
                }if(s&1) ans += m/tmp;
                else ans -= m/tmp;
            }
        }printf("%lld\n", ans);
    }
    return 0;
}