2013
12-21

# 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.

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

#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作为参数。