CF1878 F.Vasilije Loves Number Theory
题解：约数个数 + 取模性质
- 对\(n\)质因子分解得到，\(n =p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}\)
- 那么显然\(d(n) = (\alpha_1 + 1)\times (\alpha_2 + 1) ... (\alpha_k + 1)\)
- 根据题意可以得到：\(n \% d(n) = 0\)的时候一定存在一个正整数\(a\)使得题目要求成立
- 那么现在的问题在于怎么判断\(n \% d(n) = 0\)，因为\(n\)可能很大，所以我们不妨利用取模的性质：$a \times b % p = a % p \times b % p $
- 所以我们只需要用\(map\)记录\(n\)中质因子及其幂次，然后快速幂即可得到\(n\)对\(d(n)\)取模后的值
int n, q;
map<int, int> mp, mp1;
ll qpow(ll a, ll b, ll p)
{
ll res = 1;
while (b)
{
if (b & 1)
res = (__int128)res * a % p;
a = (__int128)a * a % p;
b >>= 1;
}
return res;
}
void solve()
{
cin >> n >> q;
mp.clear(), mp1.clear();
for (int i = 2; i <= n / i; ++i)
{
while (n % i == 0)
{
mp[i]++;
n /= i;
}
}
if (n > 1)
mp[n]++;
mp1 = mp;
while (q--)
{
int op, x;
cin >> op;
if (op == 1)
{
cin >> x;
for (int i = 2; i <= x / i; ++i)
{
while (x % i == 0)
{
mp1[i]++;
x /= i;
}
}
if (x > 1)
mp1[x]++;
int sum = 1;
for (auto [a, b] : mp1)
sum *= (b + 1);
int r = 1;
for (auto [a, b] : mp1)
r = r * qpow(a, b, sum) % sum;
if (r % sum == 0)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
else
mp1 = mp;
}
cout << endl;
}
CF1851 G. Vlad and the Mountains
题解：离线 + 并查集
- 我们观察性质：如果我们从\(i\)移动到\(j\)，代价为\(h[j] - h[i]\)，然后我们再从\(j\)移动到\(k\)，代价为\(h[k] - h[j]\)，所以易得从\(i\)移动到\(k\)，代价为\(h[k] - h[i]\)
- 所以，容易证明从任意一个点\(i\)移动到任意另一个点\(j\)，代价为\(h[j] - h[i]\)
- 那么题目就转化为：从\(a\)点移动到\(b\)点，且经过的点的点权必须\(\leq h_a + e\)
- 这是一个经典的问题
- 显然我们可以将询问离线后进行排序，然后利用并查集判断即可
int n, m, q, fa[N], a[N];
array<int, 2> h[N];
vector<int> g[N];
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
int fx = find(x), fy = find(y);
if (fx != fy)
fa[fx] = fy;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
fa[i] = i, g[i].clear();
for (int i = 1; i <= n; ++i)
{
cin >> h[i][0];
h[i][1] = i;
a[i] = h[i][0];
}
for (int i = 1; i <= m; ++i)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> q;
vector<array<int, 4>> qry;
for (int i = 1; i <= q; ++i)
{
int u, v, e;
cin >> u >> v >> e;
qry.push_back({h[u][0] + e, u, v, i});
}
sort(h + 1, h + n + 1);
queue<array<int, 2>> que;
for (int i = 1; i <= n; ++i)
que.push(h[i]);
sort(all(qry));
vector<int> ans(q + 10);
for (auto [x, u, v, qid] : qry)
{
// cout << x << " " << u << " " << v << " " << qid << endl;
while (que.size() && que.front()[0] <= x)
{
int u = que.front()[1];
que.pop();
for (auto v : g[u])
{
if (a[v] <= x)
merge(u, v);
}
}
if (find(u) == find(v))
ans[qid] = 1;
else
ans[qid] = 0;
}
for (int i = 1; i <= q; ++i)
{
if (ans[i])
cout << "YES" << endl;
else
cout << "NO" << endl;
}
cout << endl;
}
CF1841 D. Pairs of Segments
\(2 \leq n \leq 2000\)
题解：最大不相交区间数
- 显然我们可以\(O(n^2)\)将所有的相交的线段合并成一个线段
- 然后就是一个经典的问题：在一些区间中，求最大不相交区间个数
- 显然按照右端点排序后遍历一遍即可
int n;
array<int, 2> seg1[N], seg[M];
void solve()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
int l, r;
cin >> l >> r;
seg1[i] = {l, r};
}
int idx = 0;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
{
auto [l1, r1] = seg1[i];
auto [l2, r2] = seg1[j];
if (r2 >= l1 && l2 <= r1)
seg[++idx] = {max(r1, r2), min(l1, l2)};
}
sort(seg + 1, seg + idx + 1);
int now = 0, sum = 0;
for (int i = 1; i <= idx; ++i)
{
auto [r, l] = seg[i];
if (i == 1)
now = r, sum++;
else if (l > now)
now = r, sum++;
}
cout << n - 2 * sum << endl;
}