Wicky Roam's Blog

昨天哈工程的网络预赛1004，数论题，关于具体推导可以看这里（牛人的数学证明）：

重点是Hint：

Hint:The number n never has a prime factor greater than 13000000, but n may be extremely large。

所以说具体实现要用到高精度除法，大概就是检查这个数可不可以被13000000以内的质数平方整除，问题就在这里，一般来说素数筛法是O(n)的，那么在哈工程的评测机上生成质数表就需要0.65秒，而后再用高精试除，但是这个素数表有84W+的质数，再加高精确实超时。

但事实上只要判断2-sqrt(13000000)之间的素数就可以了，为什么？因为他的题出错了，而且改了之后还错上加错，上面的Prime是后来加上去的，因为出题人发现了这道题的错误，测试数据里大概有诸如

2*3*5*7*…*101>>13000000的数据，他开始大概认为这个数据没有大于13000000的因子，因为他这样想：这个数的两两质因子的乘积都小于13000000，所以这是正确的，但后来有人在讨论版提问，他想了想，似乎不对呀。于是加上了prime，这样的话数据规模就不得了了，但是他应该也没有想过这个问题，所以没有再改数据范围，其实正确的Hint是：

Hint:The number n never has a prime factor greater than sqrt(13000000), but n may be extremely large。

OMG！我的AC啊，就这样没了，早知道当时我也应该怀着侥幸心理就能把这道题搞定了！另外我更希望现场赛不再有这种情况。