数论两题 POJ2429 POJ1930

每次看到辗转相除法就有一点小伤感. 昨天写了一小段话没保存, 不见了. 所以为什么伤感就按照上天的意思不写了罢.

已知GCD和LCM求AB.

我想了一会想不通, 然后跑到码农场看题解, 然后吓一跳. 发现这个题对我这貌似一道数学题都没做过的人来说有点难了.

作者显然高估了读者的数学修养，我对数论一点都不熟悉，这题光靠前面介绍的一点数论皮毛无从下手，还是看了人家的代码才知道要用Rabin-Miller强伪素数测试和Pollard – rho因数分解算法。这两个算法的详解放在最后面，不时回来复习一下。

基本思路就是对 lcm/gcd 这个数进行因数分解, 然后dfs找符合题意的最大值.
然后就去看这篇文章, 看了半天有点晕, 还是边敲代码边理解吧.

为了偷懒, 用了kuangbin 的模板, 浏览模板的时候感觉写的真棒..

…..N小时….各种WA

妈的把我累死了.

终于过了.

我有时候想, 数论题是不是给以前玩过奥数的人加分用的.
感觉范围太广了.
根据提示, 去百度百科看了一下小数循环节的知识. 再通过若干人的题解避开了题目中没提循环节是多少位的坑, 剩下的就是自己写一个枚举程序.

WA了几回之后感觉不同类型的题目的WA点还真的可以如此不一样.