Test20231016

发布时间 2023-12-23 17:21:35作者: Mu_leaf

考得真烂。被初一dalao薄纱。

[题面+std](https://www.wenshushu.cn/drive/cfraky1du37)。

T1:数学结论题:裴蜀定理,即:$a \times x + b \times y =\gcd(a,b)$

T2:小清新贪心题,清楚一点性质**从点 $i\to j(j>i)$ 然后又从点 $j\to k(j>k)$ 那么为什么不能从 $i$ 直接到 $k$ 呢?**

根据这点限制,于是我们就可以写贪心,其中的贪心策略便可以钦定为:要么你选第 $n+1$ 点或者选第一个能走的比当前点远的点,或者操作该点。

T3:

对于任何一个正整数 $n$ 都可以表示成 $a\times {k^3}$ 的形式,其中 $k$ 是 $n$ 最大的立方因子。
如果 $a$ 是 $n$ 去掉最大立方因子后的结果,$b$ 是 $m$ 去掉最大立方因子后的结果,如果 $n\times m$ 是立方数,则 $a\times b$ 也是立方数,且 $a$ 和 $b$ 是唯一配对的。
例如 ${2,16,54,686}$ 在去除立方因子后全部等于 $2$ ,然后 ${4,32,108,1372}$ 在去除立方因子后全部等于 $4$。
所以 ${2,16,54,686}$ 中的任意一个数字乘上 ${4,32,108,1372}$ 中的任意一个数字都是一个立方数。

一开始输入数字,筛除掉它们的立方因子,然后统计每种数字出现次数。
然后对于每一对出现的种类,都是两两互斥的,所以贪心的取出现次数较多的部分即可。

T4:
有点细节问题挂 $50pts$。还算简单。