设S(g,n)代表gcd=g,已添加原料个数=n的状态。E(g,n)代表继续添加原料个数的期望。那么原题就是求E(g,0)。
对g分解因数,得到g的质因数列表a[t],对应指数列表b[t],有
g = a0^b0 + a1^b1 + ... + at^bt,
于是,后继的g能表示为
g' = a0^c0 + a1^c1 + ... + at^ct,其中ci满足0<=ci<=bi
接下来要遍历[c0,c1,...ct]的组合,算出每种组合的概率P((g',n+1)|(g,n))和期望E(g',n+1),相乘再累加,就得到了要求的E(g,n)
概率P((g',n+1)|(g,n))的计算:
1.如果bi>ci,则将对应的ai记入集合d
2.从1~int(m/g')的整数中,筛掉集合d的成员的倍数。剩余数字的个数cnt,即为S(g,n)->S(g',n+1)的途径数
3.S(g,n)时,有m-n个数可选。因此概率为cnt/(m-n)
期望E(g',n+1)的计算:
递归。显然递归次数小于m,能在有限步内完成。可以开个hashmap做缓存
递归的边界条件:
1. g=1时,不用继续。E(1,x) = 0
2. n>=m/g时,g的倍数全部加进S了,下个g一定变小。P((g,n+1)|(g,n)) = 0
例如,m=100时,求E(60,1)
1. 60 = 2^2 * 3^1 * 5^1, 得 a=[2,3,5], b=[2,1,1],需遍历(2+1)*(1+1)*(1+1)=12种状态
2. 以c=[1,0,1]为例,这时g‘= 2^1 * 5^1 = 10,对应S(10,2)
a) b0>c0, b1>c1, b2=c2, 得到的集合d为{a0,a1} = {2,3}
b) 从不超过100/10=10的整数中,去掉2和3的倍数,剩余3个数(即1,5,7)。所以有3个数能使g变成10(即10,50,70)
c) result += 3 * E(10,2),这一步要递归计算E(10,2)
3. c的遍历结束后,result/(100-1),就是E(60,1)
那个复杂度估得很松:因为E(g,0)有两个维度,可能要计算g*m个状态。如果g m成比例,就成了m^2。再假设每个子状态需要k~mk次运算,相乘就是m^2~m^3