2019 Multi-University Training Contest 3
补题链接:2019 Multi-University Training Contest 3
1002 Blow up the city (HDU-6604)
题意
给定 $n$ 个点和 $m$ 条边的有向无环图,给出 $q$ 次询问,每个询问给出 $a$ 和 $b$,求有多少个点,满足该点删去后 $a$ 和 $b$ 中至少一个点不能到达出度为 $0$ 的点。
题解
支配树/灭绝树 拓扑排序 最近公共祖先
1006 Fansblog (HDU-6608)
题意
给定素数$ P(1e^9\leq P\leq 1e^{14})$,试找出小于$P$的最大素数$ Q$,求出$ Q! mod P$。
题解
威尔逊定理 逆元 质数的密度分布 Miller-Rabin素数测试
威尔逊定理:当且仅当 $P$ 为素数时:$(P - 1)!\equiv -1 mod P$
即 $(P-1)!\equiv(P-1) mod P$,由于 $(P - 1)! = (Q!) \cdot (Q + 1) \cdot (Q + 2) \cdot … \cdot (P - 1)$,可得 $Q! mod P=\frac {(P - 1)}{(Q + 1) \cdot (Q + 2) \cdot … \cdot (P - 1)} mod P=\frac {1}{(Q + 1) \cdot (Q + 2) \cdot … \cdot (P - 2)} mod P$
可以使用 $Miller-Rabin$ 素数测试判断素数,也可直接使用试除法。
素数间的间隔不超过 $600$ (素数间的大间隔(Large gaps between primes)),因此可直接从 $P - 1$ 开始查找 $Q$。
注意数很大,需要使用快速乘。(WA了好几发)
代码: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
using namespace std;
typedef unsigned long long ll;
ll mulmod(ll a, ll b, ll m) {
ll ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % m;
a = (a << 1) % m;
b >>= 1;
}
return ans % m;
}
ll qmod(ll a, ll b, ll m) {
if(!b) return 1 % m;
ll ans = 1;
while (b) {
if (b & 1) ans = mulmod(ans, a, m);
a = mulmod(a, a, m);
b >>= 1;
}
return ans % m;
}
bool Miller_Rabbin(ll n, ll a) {
ll d = n - 1, s = 0, i;
while (!(d & 1)) {
d >>= 1;
s++;
}
ll t = qmod(a, d, n);
if (t == 1 || t == -1)
return 1;
for (i = 0; i < s; i++) {
if (t == n - 1)
return 1;
t = mulmod(t, t, n);
}
return 0;
}
bool is_prime(ll n) {
ll i, tab[4] = {3, 4, 7, 11};
for (i = 0; i < 4; i++) {
if (n == tab[i])
return 1;
if (!n % tab[i])
return 0;
if (n > tab[i] && !Miller_Rabbin(n, tab[i]))
return 0;
}
return 1;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
ll n;
scanf("%lld", &n);
for (ll i = n - 1;; --i) {
if (is_prime(i)) {
ll ans = 1;
for (ll j = i + 1; j <= n - 2; ++j) {
ans = mulmod(ans, qmod(j, n - 2, n), n);
}
ans = (ans + n) % n;
printf("%lld\n", ans);
break;
}
}
}
return 0;
}
1007 Find the answer (HDU-6609)
题意
给定 $n$ 个整数 $W_i(1\leq i\leq n)$ 和一个整数 $m$,对于每个$ i(1\leq i \leq n)$,求至少需要删除多少个 $W_k(1\leq k < i)$,使得$\sum_{j=1}^iW_j\leq m$。其中 $1\leq W_i\leq m(1\leq i\leq n)$
题解
multiset STL
神仙做法
1 |
|