链接：https://codeforces.com/contest/2125
A. Difficult Contest
算法：
模拟，构造。
思路：
题目要求一个字符串中不能包含 \(FFT\) 和 \(NTT\) 连续子串，考虑到两个连续子串中 \(T\) 都是在结尾，所以只需先把所以 \(T\) 输出了即可。
关键代码：
void solve()
{
string s;
cin >> s;
int n = s.size();
vector<int> st(n + 10, 0);
for (int i = 0; i < n; ++i)
{
if (s[i] == 'T')
{
cout << 'T';
st[i] = 1;
}
}
for (int i = 0; i < n; ++i)
{
if (!st[i])
cout << s[i];
}
cout << endl;
}B. Left and Down
算法：
数学，\(gcd\)。
思路：
不难发现答案不会超过 \(2\)，当我们使用 \((0, 1)\) 共 \(a\) 次，\((1, 0)\) 共 \(b\) 次，总能到达\((0, 0)\)。
所以只需判断什么时候可以在成本为 \(1\) 到达目的地。
所以我们只需判断有没有一个数对 \((dx, dy)\)，使得使用多次该数对，可以直接到达目的地。既是否存在 \(t\) 使得 \((a = t * dx, b = t * dy)\) 成立，既如果存在 \(\frac{a}{t} \leq k\) 且 \(\frac{b}{t} \leq t\)，就可以在成本为 \(1\) 到达目的地，可以发现 \(t\) 是 \(a\) 和 \(b\) 的公约数，所以只需检查 \(a\) 和 \(b\) 的 \(gcd\) 即可。
关键代码：
void solve()
{
ll a, b, k;
cin >> a >> b >> k;
ll d = __gcd(a, b);
ll dx = a / d, dy = b / d;
ll maxx = max(dx, dy);
if (maxx <= k)
cout << 1 << endl;
else
cout << 2 << endl;
}C. Count Good Numbers
算法：
容斥原理。
思路：
首先从优质数的定义下手，优质数是一个正整数的质因数分解中所有质数都至少包含两位数，不难发现只有不被小于 \(10\) 的质数整除 \((2, 3, 5, 7)\) 的数才是优质数，既寻找 \(l \text{ ~ } r\) 内不被 \(2,3,4,7\) 整除的数，这类问题可以使用容斥原理快速计算。
我们定义一个函数 \(count(n)\) 表示从 \(1\) 到 \(n\) 中有多少个优质数。为了计算它，我们可以先求出从 \(1\) 到 \(n\) 中被 \(2,3,4,7\) 整除的数的个数，用 \(n\) 减去这个数量就是优质数的个数。
具体地，我们使用容斥原理，依次减去包含一个质数因子的数量，补回来包含两个质数因子的重复部分，依此类推：
- 减去：\(n / 2、n / 3、n / 5、n / 7\)
- 加上：\(n / 6、n / 10、n / 14、n / 15、n / 21、n / 35\)
- 减去：\(n / 30、n / 42、n / 70、n / 105\)
- 加上：\(n / 210\)
这样计算出的 \(count(n)\) 就是 \([1, n]\) 中的优质数数量。使用 \(count(r) – count(l – 1)\) 就是 \([l, r]\) 中的优质数数量。
关键代码：
void solve()
{
ll l, r;
cin >> l >> r;
auto get = [](ll n) -> ll
{
return n - n / 2 - n / 3 - n / 5 - n / 7 + n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35 - n / 30 - n / 42 - n / 70 - n / 105 + n / 210;
};
cout << get(r) - get(l - 1) << endl;
}D. Segments Covering
敬请期待。
