Difference between revisions of "2020 CCPC Weihai Onsite"

From EOJ Wiki
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$ ,使得这些数的乘积最大

那么将每一个质数当作物品,做一个背包即可