本文同时作为在炼石计划 NOIP 2025 阶段的讲稿。
- 欧几里得算法
- P11846
- P9193
- 扩展欧几里得算法
- P5179
- 类欧几里得算法
- P5172
- 万能欧几里得算法
- CF868G
- SB 树
- AT_agc051_f
欧几里得算法
P11846
初始时给定两个整数 \(a,b\),在一次操作内可以将一个数加上另外一个数,给定 \(c,d\),求最少操作次数使得 \(a=c,b=d\) 或输出无解。
\(\texttt{Data Range:}\;Q\le 10^5,|a|,|b|,|c|,|d|\le 10^{18}\)。
P9193
考虑如下代码:
string gen_string(int64_t a, int64_t b) {string res;int ia = 0, ib = 0;while (ia + ib < a + b) {if ((__int128)ia * b <= (__int128)ib * a) {res += '0';ia++;} else {res += '1';ib++;}}return res; }
定义一个字符串是好的当且仅当其能被一组 \(a,b\) 生成,给定 \(a,b\),求它们对应的字符串中好的字符串的前缀数量。
\(\texttt{Data Range:}\;T\le 10,a,b\le 10^{18}\)。
扩展欧几里得算法
P5179
求最简分数 \(\dfrac{p}{q}\) 满足 \(\dfrac{a}{b}<\dfrac{p}{q}<\dfrac{c}{d}\),在此基础上最小化 \(q\),然后再最小化 \(p\)。
\(\texttt{Data Range:}\;T\le 500,a,b\le 10^9\)。
类欧几里得算法
P5172
给定 \(d,r\),求 \(\sum\limits_{d=1}^{n}(-1)^{\left\lfloor d\sqrt{r}\right\rfloor}\)。
\(\texttt{Data Range:}\;t\le 10^4,n\le 10^9,r\le 10^4\)。
万能欧几里得算法
CF868G
有 \(n\) 个洞穴,有一个洞穴有宝藏。每一天选取 \(k\) 个洞穴挖掘,如果选中了宝藏所在洞穴则以 \(\dfrac{1}{2}\) 概率结束。求最优策略下期望结束天数。
\(\texttt{Data Range:}\;T\le 1000,n,k\le 5\times10^8\)。
SB 树
AT_agc051_f
有两个沙漏,一个计时 \(1\) 秒,一个计时 \(\sqrt{2}\) 秒,\(Q\) 次询问能否计量出 \(x_i+y_i\sqrt{2}\) 秒。
\(\texttt{Data Range:}\;Q\le 10^5,|x_i|,|y_i|10^9\)。