abc212 差F
A - Alloy (5')
B - Weak Password (64')
C - Min Difference (246')
两个数组中各取一数，最小化差的绝对值
排序，各用一个指针
D - Querying Multiset (775')
三种操作：加入一个数x、所有数+x、输出并删除最小数
小根堆，维护全局add
E - Safety Journey (1410')
n个点的完全图删去m条边，问从点1出发最终回到点1的路径数。没有重边。n,m,k<=5000
如果是加边而不是删边，那大力dp就行了（迭代k次）
删边的话就用完全图来减
F - Greedy Takahashi (2332')
第 \(i\) 趟大巴在 \(s_i\) 时刻从 \(a_i\) 城市出发，并在 \(t_i\) 时刻到达 \(b_i\) 城市。每次询问在 \(x_i\) 时刻从 \(y_i\) 城市出发，等到车就上，在 \(z_i\) 时刻会在哪趟车或哪个城市。范围 \(1e5\)
啊？居然是倍增？
对城市+时间倍增是不现实的，应该对大巴倍增
倍增、二分要考虑边界问题啥的，我觉得还是有一点细节的吧。。调完代码之后看了下 tourist 的，他的代码真是优雅
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 18;
int n, m, q, f[N][M];
array<int, 4> bus[N];
vector<pair<int, int> > city[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= m; i++) {
auto &[a, b, s, t] = bus[i];
cin >> a >> b >> s >> t;
city[a].push_back({s, i}); // startTime, busId
}
for (int i = 1; i <= n; i++)
sort(city[i].begin(), city[i].end());
// 计算 f[u][0]
for (int u = 1; u <= m; u++) {
auto [a, b, s, t] = bus[u];
auto p = lower_bound(city[b].begin(), city[b].end(), make_pair(t, 0));
f[u][0] = p == city[b].end() ? u : p->second; //留在原地或接着坐下一趟车
}
// 计算 f[u][1~18]
for (int i = 1; i < M; i++) {
for (int u = 1; u <= m; u++)
f[u][i] = f[f[u][i - 1]][i - 1];
}
while (q--) {
int x, y, z;
cin >> x >> y >> z;
auto p = lower_bound(city[y].begin(), city[y].end(), make_pair(x, 0));
if (p == city[y].end() || p->first >= z) { //完全坐不了车
cout << y << '\n';
} else {
int t = p->second;
for (int i = M - 1; i >= 0; i--) { //旅途中的最后一趟车
if (bus[f[t][i]][2] < z) t = f[t][i];
}
if (bus[t][3] >= z) cout << bus[t][0] << ' ' << bus[t][1] << '\n'; //最后在车上
else cout << bus[t][1] << '\n'; //最后在目的地
}
}
return 0;
}
G - Power Pair (2150')
原根还真能出题啊？长见识了
给定质数 \(p(\le 10^{12})\)，询问有多少对 \(x,y\) 满足 \(0\le x, y\le p-1\) 且存在 \(m\) 使得 \(x^m\equiv y\pmod p\)
设 \(g\) 为模 \(p\) 的一个原根，那么 \(g^{1..p-1} \mod p\) 取遍 \(1..p-1\)，那么 \(x,y\) 都可写成 \(g\) 的幂 \(x=g^a, y=g^b\) （这里假设 \(x,y>0\)）
那么 \(g^{am}\equiv g^b \pmod p\) 即 \(am\equiv b\pmod {p-1}\)，注意模数是 \(p-1\)。下面记 \(n=p-1\)
此式有解当且仅当 \(\gcd(a,n)|b\)，那么答案为 \(\sum\limits_{a=1}^{n}\frac {n}{\gcd(a,n)} = \sum\limits_{d|n}\frac {n}d f(d)\)，其中 \(f(d)\) 表示 \([1,n]\) 中与 \(n\) 的 \(\gcd\) 是 \(d\) 的数有几个，实际上 \(f(d)=\varphi(\frac{n}d)\)。那么答案就是 \(\sum\limits_{d|n}d \varphi(d)\)
还有 \(x=y=0\) 的情况，最终答案记得 \(+1\)
看网上的题解好像直接求 \(\varphi\) 也能过，复杂度不太懂
官方题解：\(f(d)=\frac nd - \sum\limits_{d\neq x\and d|x}f(x)\)，于是从大到小计算 \(f(d)\)，复杂度 \(d^2\)
另外 AcWing 有个 \(O(质因子数*因子数)\) 的写法，我看了半天。居然也刚好不重不漏诶！真神奇
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
void add(ll &x, ll y) {
x = ((x + y) % mod + mod) % mod;
}
int main() {
ll n;
cin >> n;
n--;
vector<ll> ds;
for (ll i = 1; i <= n / i; i++) if (n % i == 0) {
ds.push_back(i);
if (i != n / i) ds.push_back(n / i);
}
sort(ds.begin(), ds.end());
vector<ll> f(ds.size());
ll ans = 1;
for (int i = ds.size() - 1; i >= 0; i--) { //O(d^2)
f[i] = n / ds[i];
for (int j = i + 1; j < ds.size(); j++) {
if (ds[j] % ds[i] == 0) f[i] -= f[j];
}
f[i] %= mod;
ans += n / ds[i] % mod * f[i] % mod;
}
cout << (ans % mod + mod) % mod;
return 0;
}