本文主要是介绍BZOJ 1025 游戏 DP+lcm+素数筛选,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
排数=lcm{Ai,Ai表示循环节长度},sum(Ai)=n根据lcm的定义,分解质因数拆掉Ai=p1^x1*p2^x2*...*pk^xklcm=∏(pi^max{xi})所以我们只看max{xi}即可,即忽略掉≤max{xi}的其它因子。所以问题等价于:sum(pi^xi)≤n的方案数。然后随便dp即可设d(i,j) 表示前i个质数和为j的方案,有d(i,j)=d(i−1,j)+sum(d(i−1,j−pi^k))这篇关于BZOJ 1025 游戏 DP+lcm+素数筛选的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!