A. EhAb AnD gCd
给定 \(x\) 求解任意一个数对 \((a,b)\) 使得 \(gcd(a,b)+lcm(a,b) = x\)
\(1\le a,b\le1e9,2\le x\le1e9\)
签到，\(a,b\) 可以为 \(1\) 所以直接输出 \(1,x - 1\) 即可
void AC() {
int x; cin >> x;
cout << 1 << ' ' << x - 1 << endl;
}
如果 \(2\le a,b\) 的话，可以分奇偶讨论，偶数输出 \(x/2,x/2\)，奇数表示为 \(1+(x-1)\) ，\(x-1\) 质因数分解后表示为两个数乘积即为 \(a,b\)
本题还能够求解对于 \(x\) 满足条件的 \(a,b\) 方案数
\(g+\frac{ab}{g}=x\)
\(g^2+ab=g^2+k_1g·k_2g=(1+k_1k_2)g^2=gx\)
\(k_1k2=\frac{x}{g}-1\)
枚举 \(g\) 满足 \(g|x\)，统计 \(x/g-1\) 的因子对数
B. CopyCopyCopyCopyCopy
给定 \(n\) 个数的数组，并在末尾添加原数组的复制 \(n\) 次，求序列 LIS
\(1\le n\le1e5,1\le a_i\le1e9\)
输出序列去重后元素个数
void AC() {
int n; cin >> n;
vector<int> v(n);
for (auto& i : v) cin >> i;
sort(all(v));
int len = unique(all(v)) - v.begin();
cout << len << endl;
}
C. Ehab and Path-etic MEXs
给定一棵 \(n\) 结点的树，使用 \([0,n-2]\) 给所有边标号，最小化所有可能路径 MEX 的最大值
\(1\le n\le1e5\)
树上任意两个点（边）总有路径相连，所以答案至少为 \(2\ (MEX\{0,1,....\})\)
题意转化成构造不含包括 \(0,1,2\) 路径的方案
要让三条边不出现在同一路径里，一个简单的方法就是选择一个度数大于等于 \(3\) 的结点出发的任意 \(3\) 条边
int a[N];
vector<pii> vt[N];
void AC() {
int n; cin >> n;
for (int i = 1; i <= n - 1; ++i) {
int u, v; cin >> u >> v; a[i] = -1;
vt[u].push_back(make_pair(v, i));
vt[v].push_back(make_pair(u, i));
}
int mx = vt[1].size(), p = 1, idx = 0;
for (int i = 2; i <= n; ++i) {
if (vt[i].size() > mx) {
mx = vt[i].size(); p = i;
}
}
for (auto e : vt[p]) a[e.second] = idx++;
for (int i = 1; i <= n - 1; ++i) {
if (a[i] == -1) a[i] = idx++;
}
for (int i = 1; i <= n - 1; ++i) cout << a[i] << endl;
}
D. Ehab the Xorcist
给定 \(u,v\) ，构造最短的数组使 \(\oplus_{1}^{n}=u,\sum_{1}^{n}=v\)
\(0\le u,v\le1e18\)
异或和奇偶性等于求和，异或和小于等于求和；根据这两个条件判断无解
根据异或 \(2\) 次抵消的性质可以构造出长度 \(3\) 的解 \(\{u,(v-u)/2,(v-u)/2\}\)
当 \(u,(u-v)/2\) 不存在相同数位的 \(1\) 时可以合并
void AC() {
int x, s; cin >> x >> s; //xor,sum
if (x % 2 != s % 2 || x > s) {
cout << -1 << endl;
return;
}
if (s == 0) {
cout << 0 << endl;
return;
}
if (x == s) {
cout << 1 << endl << s << endl;
return;
}
int d = (s - x) / 2;
if (x & d) { cout << 3 << endl << d << ' ' << d << ' ' << x << endl; }
else { cout << 2 << endl << (x ^ d) << ' ' << d << endl; }
}
补题：
E. Ehab's REAL Number Theory Problem
给定 \(n\) 个数的数组，求最短的子序列使其积为完全平方数，输出子序列长度
\(1\le n\le 1e5,1\le a_i\le1e6\) 且 \(a_i\) 因子数小于等于 \(7\)
选择顺序不影响乘积，当作选一个子集就行
有 \(3\) 个质因子时有至少 \(8\) 个因子，所以每个 \(a_i\) 分解质因数后只有 \(3\) 种情况 \(1,p,pq\)；
完全平方数分解质因数后每个质因子为偶数次幂，所以我们要取一些满足条件的数
用 \(1e6\) 范围内的所有素数建图，将数组中的数放在边上，这样选择子数组就变为图上的一条路径
当 \(a_i\) 本身为素数时连边 \(1,p\)；否则连边 \(p,q\)
如果有自环和重边处理比较麻烦，刚好发现这些情况在本题中对应特殊情况，预先判掉不让它们出现
这样我们需要的路径需要满足：经过（出、入）路径上每一个点两次，只有环满足；求图上最小环即可
然而常见最小环算法无论是 \(dij\) 还是 \(floyd\) 都不好做；
发现答案的最小因子一定不超过 \(\sqrt{1e6}=1000\) 只需枚举包含 \([1,1000]\) 中素因子的环；
由于边权均为 \(1\)，线性的 \(bfs\) 即可，\(dij\) 卡卡应该勉强可过
如果要输出方案，往边里多加一个信息
const int N = 1e5 + 5, M = 1e6 + 5;
bitset<M + 5> is_prime;
int prime[M + 5];
void get_prime() {
is_prime.set(); is_prime[0] = is_prime[1] = 0;
int cnt = 0;
for (int i = 2; i <= M; ++i) {
if (is_prime[i]) prime[++cnt] = i;;
for (int j = 1; j <= cnt; ++j) {
if (i * prime[j] > M) break;
is_prime[i * prime[j]] = 0;
if (i % prime[j] == 0) break;
}
}
prime[0] = cnt;
}
struct prime_factor { ll p, k; };
void get_pf(ll n, vector<prime_factor>& pf) {
pf.clear();
for (int i = 1; i <= prime[0] && prime[i] * prime[i] <= n; ++i) {
if (n % prime[i] == 0) {
int t = 0;
while (n % prime[i] == 0) n /= prime[i], ++t;
if (t & 1) pf.push_back({ prime[i],t });
}
}
if (n > 1) pf.push_back({ n,1 });
}
bool vis[M];
int dis[M];
vector<int> vt[M];
int bfs(int s) {
int ans = INT_MAX;
queue<pii> q; vector<int> his;
dis[s] = 0; vis[s] = 1;
his.push_back(s); q.push(make_pair(s, 0));
while (q.size()) {
int u = q.front().first, p = q.front().second;
q.pop();
for (auto v : vt[u]) {
if (v == p) continue;
if (vis[v]) {
ans = min(ans, dis[u] + dis[v] + 1);
}
else {
dis[v] = dis[u] + 1; vis[v] = 1;
his.push_back(v); q.push(make_pair(v, u));
}
}
}
for (auto u : his) vis[u] = 0;
return ans;
}
void AC() {
get_prime();
int n; cin >> n;
int ans = INT_MAX;
vector<int> a(n);
for (auto& i : a) cin >> i;
for (auto x : a) {
vector<prime_factor> pf; get_pf(x, pf);
if (vis[x]) {
ans = min(ans, 2ll);
continue;
}
vis[x] = 1;
if (pf.size() == 0) { //本身是1或者平方数
cout << 1 << endl;
return;
}
if (pf.size() == 1) {
vt[1].push_back(pf[0].p);
vt[pf[0].p].push_back(1);
}
else {
vt[pf[0].p].push_back(pf[1].p);
vt[pf[1].p].push_back(pf[0].p);
}
}
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= 1000; ++i) ans = min(ans, bfs(i));
cout << (ans == INT_MAX ? -1 : ans) << endl;
}
F. Ehab's Last Theorem
给一个无向图，保证图连通且不包含自环和重边 要求输出以下两种其中一种
1.包含 \(\lceil \sqrt n\rceil\) 个结点的独立集
2.包含至少 \(\lceil \sqrt n\rceil\) 个结点的简单环
\(1\le n\le1e5\)
复习了一下 dfs 树，有向图中 dfs 树上成环的原因有返祖边、横叉边
而在无向图中，前向边和返祖边可以视作一样，横叉边则不存在（因为在无向图中，原本有向图的横叉边会先被访问到而变成一个正常的树边）
所以只剩下返祖边的成环，在dfs过程中遇到已访问的结点就是遇到环
如果不存在 2 那么 1 一定成立，从下到上类似染色地取就行
证明：根据鸽巢定理，每个点一定不会有大于 \(\lceil \sqrt n \rceil-2\) 条回边，这是因为一旦有 \(\lceil \sqrt n \rceil-1\) 条，则肯定能联通 \(\lceil \sqrt n \rceil\) 个点（取最劣的就是深度依次小1，小2...），那么就存在满足条件的环
int n, m, sq;
bool flag = 0;
int dep[N], fa[N];
vector<int> vt[N];
vector<int> cyc;
void dfs(int u, int d) {
if (flag) return;
dep[u] = d;
for (auto v : vt[u]) {
if (!dep[v]) {
fa[v] = u;
dfs(v, d + 1);
}
else if (!flag && dep[u] - dep[v] + 1 >= sq) {
depair("->", u, v, "\n");
int cur = u;
while (cur != fa[v]) {
cyc.push_back(cur);
cur = fa[cur];
}
flag = 1; return;
}
}
}
int vis[N], col[N];
vector<int> is;//independent set
void dfs1(int u) {
vis[u] = 1;
for (auto v : vt[u]) {
if (!vis[v]) dfs1(v);
}
if (!col[u]) {
for (auto v : vt[u]) col[v] = 1;
}
}
void AC() {
cin >> n >> m; sq = ceil(sqrt(n));
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
vt[u].push_back(v);
vt[v].push_back(u);
}
dfs(1, 1);
if (flag) {
cout << 2 << endl;
cout << cyc.size() << endl;
for (auto i : cyc) cout << i << ' ';
return;
}
dfs1(1);
for (int i = 1; i <= n; ++i) if (!col[i]) is.push_back(i);
is.resize(sq);
cout << 1 << endl;
for (auto i : is) cout << i << ' ';
}