数论再三题

数论再三题 POJ3126 POJ3421 POJ3292

POJ 3126 Prime Path

这道题挺棒的, 因为简单, 又用到新学的知识, 能让我一下子就想到如何解决, 而且使用的工具也不复杂.

埃氏筛+BFS

POJ 3421 X-factor Chains

质因数分解 + 组合数学

例如 36 = 2*2*3*3

对于2 2 3 3 有如下几种排列

2 2 3 3

2 3 2 3

2 3 3 2

3 2 3 2

3 2 2 3

3 3 2 2

每种排列都可以得到一种序列

2 2 3 3 –> 1 2 4 12 36

2 3 2 3 –> 1 2 6 12 36

2 3 3 2 –> 1 2 6 18 36

3 2 3 2 –> 1 3 6 18 36

….

所以质因数分解后只要求排列数就可以了.

敲了不少时间代码, 一开始为了省时间用了kuangbin的模板, 里面的强伪素数判定算法和质因数分解算法.

结果TLE.

想了想可能是强伪素数判定太慢, 需要O(1)判定. 于是打表, 然后过了.

POJ 3292 Semi-prime H-numbers

另类筛法.

挺有意思, 是学过的知识的变形运用. 就是变形的幅度对我来说稍微有点大, 其实就是因为会TLE所以要优化所以麻烦点.

优化的过程参考码农场的题解. 感觉不错.

总结: 不想做数学题, 什么都不会, 越做越觉得自己是智障.