这什么神仙题啊???

他们怎么什么都会啊???

懵逼的 题目

BZOJ

扯淡的 题解

??? 这咋做啊???

自闭了抄题解去了

看到这位大爷的题解

哦…好神奇 原来乘积超过$10^9$是没用的啊

原来$1$到$9$能乘出来的小于$10^9$的数才这么点啊

然后…

然后对于询问的x,考虑在x/Hash(k)中有多少个满足乘积为Hash(k)的即可。

????

???

怎么就[即可]了啊????

问了问yt大爷和部长大爷 知道了因为小于$10$的质数就$2, 3, 5, 7$, 所以我们可以把$Hash(k)$分解为$2, 3, 5, 7$的次方乘积, 这样就可以把这个大数放到状态里了

复杂度$O(5000 \cdot 32^4)$

据说能过

???

沙茶的 代码

// 咕咕咕

By 准备退役旅游的 Cansult