我发现最近我乱搞A了好多题.
首先我们可以发现答案随k是爆炸增长的,然后就可以想将1e18以内的合法的数全部处理出来(搜索),实际操作一下,会发现在B<10的时候是可以这么做的,但是B过大的时候1e18以内的数很多,无法全部筛出.
然后发现k<1e7,我们可以想二分答案,可以做到$O(klog1e18)$,然而复杂度过高,无法承受.
之后大约过了一个小时,突然想到,并不关注1e7以上的数,只要处理出来1e7个数即可,于是手动二分答案确定上界,即可$O(10000000)$处理.所有数据跑得一样快,所以总时间很慢.
考场上拿到了84pts,考后加了优化就AC了.
定义状态$f_{s}$表示状态为s的时候的方案数. 其中s是一个三进制数,第i位表示质因数集合为i的因数的个数.
直接记忆化搜索即可,注意我们并不关注每个因数是多少,只关注它的质因子集合,于是状态转移从$O(d(n))$减少到了$O(2^{质因子个数})$,然后就可以AC了.
随机化NB,考场上给的时间太少了.