A[J]

B[G]

统计a-b(2e9)二进制中1的个数

数位dp

比较简单的数位dp

C

D[W]

水题

E

若先手胜输出最少步数
若后手胜输出最长步数

博弈搜索

用正值表示先手获胜的步数,负值表示后手获胜的步数
在胜败态搜索的基础上加一个步数作为状态
对于后继状态,优先选负值,且尽量小,其次选正值,尽量大
然后返回是加上步数,改变正负号

F

[a,b]($2^{64}$)间有多少个数(不含前导0)满足其翻转后也在这个范围

数位dp

带上下界的数位dp
先将a长度与b补齐,前面加0

$d[len1][len2][d1][u1][d2][u2]$

表示当前数在第len1位,翻转后的数在len2位
下界当前位是否没有限制,上界当前位是否没有限制
翻转后(从第一个非0位开始计len2长度)当前数,
d2表示下界是否在范围内,d1表示上界是否在范围内

具体见代码实现

J[G]

问N(1e8)的M(1e7)次方,在多少种进制下末尾恰好有T(1e4)个0

数论

将$N^M$唯一分解,显然满足的B进制肯定可以整除$N^M$
将B也唯一分解,对于某一个质因子,设次数分别为a,b
可以产生的0个数为 $\lfloor \frac{a}{b} \rfloor$
这些b对应于 $a/(T+1),\dots,a/T$

显然末尾产生的0的个数为 $min(\lfloor \frac{a}{b} \rfloor)$

我们只需要枚举一下哪些位置上恰产生T个0,哪些位置上产生大于T个0