夺，夺少？哦，85pts，小让一手。
A. 征兵
http://222.180.160.110:1024/contest/3574/problem/1
GM 说，怕久了不打最小生成树我们给忘了。
笑话，就算退役十年我也不一定能忘了 Kruskal，就算在役十年我也不一定能记住 Prim。
就一板板题，没什么好说的。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int cos = 1e4;
const int maxn = 2e4 + 5;
const int maxm = 5e4 + 5;
struct _ {
int u, v, w;
bool operator< (const _ &q) const {
return w > q.w;
}
};
_ t[maxm];
int f[maxn];
int T, n, m, r, res;
inline void Init(int n) {
for (int i = 1; i <= n; ++i)
f[i] = i;
return;
}
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
inline void merge(int x, int y) {
f[find(x)] = find(y);
return;
}
int main() {
read(T);
while (T--) {
read(n), read(m), read(r);
for (int i = 1; i <= r; ++i) {
read(t[i].u), read(t[i].v);
t[i].v += n, read(t[i].w);
++t[i].u, ++t[i].v;
}
std::sort(t + 1, t + r + 1);
Init(n += m), res = n * cos;
for (int i = 1; i <= r; ++i) {
int fx = find(t[i].u);
int fy = find(t[i].v);
if (fx == fy)
continue;
merge(t[i].u, t[i].v);
res -= t[i].w;
}
print(res, '\n');
}
return 0;
}
} // namespace XSC062
#undef int
B. 欧拉函数的值
http://222.180.160.110:1024/contest/3574/problem/2
嘶，太久没碰数学，欧拉函数是啥？小尴一个尬。
哦哦，看完样例懂了，\(n\) 以内和 \(n\) 互质的数个数对吧。好像是用筛法求的来着。现场推一下吧。
列表可以简单地发现，若 \(n={d_1}^{p_1}\times {d_2}^{p_2} \times \cdots \times {d_k}^{p_k}\)，则 \(\phi(n) = (d_1-1)\times {d_1}^{p_1-1} \times (d_2-1)\times {d_2}^{p_2-1}\times \cdots \times (d_k-1)\times {d_k}^{p_k-1}\)。所以打个根号算法即可。
namespace XSC062 {
using namespace fastIO;
int n;
inline int phi(int n) {
int res = 1;
for (int i = 2; i * i < n; ++i) {
if (n % i == 0) {
res *= i - 1;
n /= i;
while (n % i == 0)
res *= i, n /= i;
}
}
if (n > 1)
res *= n - 1;
return res;
}
int main() {
read(n);
while (n) {
print(phi(n), '\n');
read(n);
}
return 0;
}
} // namespace XSC062
C. 龙哥的问题
http://222.180.160.110:1024/contest/3574/problem/3
龙哥 /se
G. 线性筛素数
http://222.180.160.110:1024/contest/3574/problem/7
给我十年我都不一定忘得掉欧拉筛…… woc，打挂了。还好一眼就看出来了错在哪里。
namespace XSC062 {
using namespace fastIO;
const int maxm = 5e7 + 5;
const int maxn = 1e8 + 5;
int p[maxm];
bool u[maxn];
int n, m, cnt;
inline void Euler(int n) {
u[0] = u[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!u[i])
p[++cnt] = i;
for (int j = 1; j <= cnt &&
p[j] * i <= n; ++j) {
u[p[j] * i] = 1;
if (i % p[j] == 0)
break;
}
}
return;
}
int main() {
read(n), read(m);
Euler(n);
while (m--) {
read(n);
puts(u[n] ? "No" : "Yes");
}
return 0;
}
} // namespace XSC062