引用自:http://hi.baidu.com/aekdycoin/item/be20a91bb6cc3213e3f986d3,有改动
题意:
已知D, 每次从[1,D] 内的所有素数中选择一个Ni, 如果D = 0(mod Ni), 那么D /= Ni,否则D不变(可以看成是每一轮 D/= GCD(D,Ni) )
思路:
概率DP
令 dp[ i ] 表示 D = i 的时候的期望, 即从i 转移到1 的次数期望. 我们有
p = kcnt[ i ] / cnt[ i ];
kcnt[ i ] 表示i 的素因子种类, cnt[ i ]表示[ 1..i ]内的素数总数, p 表示 D = i 时的D可以在一轮以后减小的概率, 而对于i 的每一种素因子, 取得他们的概率显然都为 1 / cnt[ i ]
假设Ni 是 i 的......
阅读全文