数论再三题

数论再三题 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所以要优化所以麻烦点.
优化的过程参考码农场的题解. 感觉不错.

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