Difference between revisions of "2020 CCPC Weihai Onsite"
Jump to navigation
Jump to search
(Created page with " == Problem A == Solved by . 00:18:00 (+) == Problem B == Unsolved. == Problem C == Solved by . 02:09:00 (+1) == Problem D == Solved by . 02:29:00 (+2) == Problem E ==...") |
|||
| (2 intermediate revisions by the same user not shown) | |||
| Line 14: | Line 14: | ||
== Problem D == | == Problem D == | ||
| − | Solved by . 02:29:00 (+2) | + | Solved by Once. 02:29:00 (+2) |
| + | |||
| + | 判断 $c$ 是否含有平方因子。我的做法是用 Pollard-Rho 去给 $c$ 做质因子分解，结果快速幂写错，而且据说板子也有问题，现在想想还有点后怕。 | ||
| + | |||
| + | 事实上判断 $c$ 是否有平方因子只需要枚举 $\sqrt[3]{c}$ 内的质数即可。 | ||
== Problem E == | == Problem E == | ||
| Line 47: | Line 51: | ||
Solved by bingoier. 01:10:00 (+2) | Solved by bingoier. 01:10:00 (+2) | ||
| + | |||
| + | 易知在最优解下一个质因子只会出现一个数字中，那么问题等价于选取若干个质数 $p_i^{k_i},k_i>=0$ ，使得这些数的乘积最大 | ||
| + | |||
| + | 那么将每一个质数当作物品，做一个背包即可 | ||
Latest revision as of 14:34, 3 November 2020
Problem A
Solved by . 00:18:00 (+)
Problem B
Unsolved.
Problem C
Solved by . 02:09:00 (+1)
Problem D
Solved by Once. 02:29:00 (+2)
判断 $c$ 是否含有平方因子。我的做法是用 Pollard-Rho 去给 $c$ 做质因子分解，结果快速幂写错，而且据说板子也有问题，现在想想还有点后怕。
事实上判断 $c$ 是否有平方因子只需要枚举 $\sqrt[3]{c}$ 内的质数即可。
Problem E
Unsolved.
Problem F
Unsolved.
Problem G
Unsolved.
Problem H
Solved by . 00:53:00 (+)
Problem I
Unsolved.
Problem J
Unsolved.
Problem K
Unsolved.
Problem L
Solved by bingoier. 01:10:00 (+2)
易知在最优解下一个质因子只会出现一个数字中，那么问题等价于选取若干个质数 $p_i^{k_i},k_i>=0$ ，使得这些数的乘积最大
那么将每一个质数当作物品，做一个背包即可