HolyNumbers

作者：王子健 汪乐平

关键词：动态规划、数学

题目简述

定义一个正整数$X$为圣光数字当且仅当$X$能写成$[1,P]$之间质数的若干奇数次幂的乘积的形式，求$[1,N]$区间中有多少圣光数字。

$1≤N≤10^{10},1≤P≤10^6$

算法

先将$[1,P]$中的所有质数预处理出来，设一共有$m$个质数，用$p[i]$表示第$i$个质数。

考虑使用动态规划来解决，设$f[i][j]$表示只考虑第$i$个到第$m$个质数，$[1,j]$中有多少数能被这些质数的若干奇数次幂的乘积表示。

转移时分两种情况，第一种是$[1,j]$中所有的数都可以用第$i+1$个到第$m$个质数的奇数次幂的乘积表示的情况，即$f[i+1][j]$。第二种先枚举$p[i]$的若干奇数次幂$k$，则符合条件的数字可以写成$k*c$的形式，且$c$要能够被第$i+1$个到第$m$个质数的若干奇数次幂的乘积表示，即$f[i+1][\lfloor \frac{j}{k}\rfloor ]$。

实际转移时有用的第二位状态并不多，因为当$p[i]p[i+1]>j$时只有满足$X=p[k](k\geq i)或1$的形式才符合要求，我们可以直接通过二分查找来计算这样的$f[i][j]$。经实测极限数据仅需调用函数不到$7*10^6$次即可。

时间复杂度约为$O(π(P)*sqrt(N))$。