bzoj3944中如何运用杜教筛和hash技巧解决哈希问题？

本文共计1245个文字，预计阅读时间需要5分钟。

这是一个常规的排序算法，按照上次的做法进行交上去，原因在于使用了map。然后，如果需要不使用map，手写hash是不可行的，所以去网上找解决方案。一个较好的方法是使用存+M。

这个是个常规的杜教筛，按上次的做法交上去会T，原因在于用了map。。。

然后需要想办法不用map，手写hash是不可能手写的，所以去网上找解决姿势。。

一个比较好的姿势是在存

和M(k)的时候可以考虑用a[n/k]这种方式存(其中n是题目要求的)

为什么可以这么存呢。。因为所有的k都是n除以一系列数得到的，而整除的顺序是对答案没有影响的，所以当把这些除数乘起来之后，枚举这些除数的积，就共有1..n这n种情况了。。

而通过预处理前m项和(m取为

)，可以将这n个数压成n/m个，即

个。。然后体验就比map好太多了。。