首页 > ACM题库 > HDU-杭电 > Hdu 1696 Help the People Been Trapped-容斥原理[解题报告] C++
2013
12-21

Hdu 1696 Help the People Been Trapped-容斥原理[解题报告] C++

Help the People Been Trapped

问题描述 :

Full Score of Fear, the Movie 12 of Detective Conan has been published recently.
Before going to the concert, Conan had been attacked and was unconscious. But Ran wasn’t aware of Conan’s disappearance. Then they went into the odeum, and the concert started.
Suddenly, the bombs in the odeum blasted and the whole building was on fire. All the audiences are trapped in the odeum, include Mouri Ran and Haibara Ai. Thousands of people are in danger now.After the explosion, some walls have collapsed and blocked the way. Now Conan gets a map from the police, and he knows the location of all the hindrances. Also, he knows that Ran is a karate superior, and she can destroy some hindrances. (Horrific) As destroying the hindrance is a hard job, Conan wants to find a way to get out of the odeum crossing the least number of hindrances.But the odeum is so large that it’s not an easy work to find that way. Can you help Conan and the people trapped in the odeum?

输入:

The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 20 cases.
Each case contains an integer M on its first line, which is the number of the hindrances. 0<=M<=4000.
The next m lines describe m hindrances each. Each line contains four integers in each, x1, y1, x2, y2, means that there is a hindrance from (x1, y1) to (x2, y2). The hindrances will not cross each other, but they can meet at the end point.
The last line contains two integers, x, y, means that the people are trapped at point (x, y). You can assume that this point will not be on any of the hindrances.
Every coordinate is between -10,000 and 10,000.

输出:

For each case, print the least number of hindrances need to be destroyed. (If you need to cross an end point, it should be counted multiple times; look at the second sample for more details) Use the format in the sample.

样例输入:

3
0
0 0
12
0 0 2 0
2 0 4 0
0 2 2 2
2 2 4 2
0 4 2 4
2 4 4 4
0 0 0 2
0 2 0 4
2 0 2 2
2 2 2 4
4 0 4 2
4 2 4 4
1 1
6
0 2 1 0
0 2 -1 0
1 0 -1 0
0 2 -2 -1
0 2 2 -1
-2 -1 2 -1
0 1

样例输出:

Case 1: Need to destroy 0 hindrances.
Case 2: Need to destroy 1 hindrances.
Case 3: Need to destroy 2 hindrances.


求(1,b)区间和(1,d)区间里面gcd(x, y) = k的数的对数(1<=x<=b , 1<= y <= d)。

b和d分别除以k之后的区间里面,只需要求gcd(x, y) = 1就可以了,这样子求出的数的对数不变。

这道题目还要求1-3 和 3-1 这种情况算成一种,因此只需要限制x<y就可以了

只需要枚举x,然后确定另一个区间里面有多少个y就可以了。因此问题转化成为区间(1, d)里面与x互素的数的个数

先求出x的所有质因数,因此(1,d)区间里面是x的质因数倍数的数都不会与x互素,因此,只需要求出这些数的个数,减掉就可以了。

如果w是x的素因子,则(1,d)中是w倍数的数共有d/w个。

容斥原理:

所有不与x互素的数的个数= 1个因子倍数的个数 – 2个因子乘积的倍数的个数 + 3个……-……

答案很大,用long long。

所有数的素因子,预先处理保存一下,不然会超时的。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define N 100005
typedef long long ll;
vector<int> x[N];
bool is[N];

void prime() {
    memset(is, false, sizeof(is));
    for (int i=0; i<N; i++) x[i].clear();

    for (int j=2; j<N; j+=2) x[j].push_back(2);
    for (int i=3; i<N; i+=2)
        if (!is[i]) {
            for (int j=i; j<N; j+=i) {
                is[j] = true;
                x[j].push_back(i);
            }
        }
}
int work(int u, int s, int w) {
    int cnt = 0, v = 1;
    for (int i=0; i<x[w].size(); i++) {
        if ((1<<i) & s) {
            cnt++;
            v *= x[w][i];
        }
    }
    int all = u/v;
    if (cnt % 2 == 0) return -all;
    else return all;
}

int main() {

    prime();

    int T, a, b, c, d, k;
    scanf("%d", &T);
    for (int cas=1; cas<=T; cas++) {
        scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
        if (k == 0) {
            printf("Case %d: 0\n", cas);
            continue;
        }
        b /= k, d /= k;

        if (b > d) { a = b; b = d; d = a; }
        long long ans = 0;
        for (int i=1; i<=d; i++) {
            k = min(i, b);
            ans += k;
            for (int j=1; j<(1<<x[i].size()); j++)
                ans -= work(k, j, i);
        }
        printf("Case %d: %I64d\n", cas, ans);
    }
    return 0;
}

 


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。