NOI Online 2022 总结与反思

## 做题过程 首先拿大约8分钟看了一遍题目，初步印象为： - T1送分（红题） - T2思维题（橙或黄题） - T3DP（绿或蓝题） 先开了T1，10分钟秒掉，没什么好说的 看了一眼T2，用草稿纸推了一下，然而发现题目好像并没有一开始想得那么简单……（看了一下数据范围，甚至没想到暴力） 我继续用草稿纸瞎推，得出了一大堆奇怪的东西 $\because x \times y \times \gcd(x,y) = z$（给定 $x$ 和 $z$） $\therefore y \times \gcd(x,y) = \dfrac{z}{x}$ $\therefore gcd(x,y)|\dfrac{z}{x}$ 进而我又想到 $\gcd(x,y)$ 是 $\gcd(\dfrac{z}{x},x)$ 的因数 看了一下数据范围，觉得可以开始枚举了（从 $\gcd(\dfrac{z}{x},x)$ 往下枚举） 测试完大样例，我就以为T2也解决掉了（危，因为大样例并不是极限数据，但我并没有发现），开T3去了 T3不知道该怎么DP，一直在各种乱想，甚至一度怀疑它不是DP，最后打了个回溯就草草了事 ## 赛后 打完了比赛才发现T2最劣是 $O(t\sqrt{x})$，预估80pts 预估分 100 + 80 + 20 = 200 pts 最终分 100 + 100 + 35 = 235 pts T2过了？？？ 应该只是数据弱侥幸过得吧 后来知道了正解，后悔自己没有把 $\gcd(x,y)$ 设为 $k$，$x$ 设为 $nk$，$y$ 设为 $mk$，推一下公式，还是数学题做得太少了 ## 总结与反思 1. 打完代码后要分析时间复杂度 1. 要检测大样例是否切合极限数据 1. 要更熟练地掌握DP和数学思维题