一个数学问题,希望和大家一起讨论一下。。
已知:递增数列 an{a1,a2,a3,...an }的函数为:a(n),
求递增数列bn{b1,b2,b3,...,bn}的函数b(n)
满足:an和bn的交集为空,an和bn的并集为所有正整数
例如:当a(n)=2n的时候,b(n)=2n-1
当a(n)=3n的时候 b(n)=3(n-1)/2+1
最简单的,a(n)=5n
求b(100) 互斥数列
[解决办法]
这个特例有O(1)的办法,b是4个数一组构成mod 5=1,2,3,4的一组。b(100)就应该是5*24+4。
对于一般的a,可以用二分的办法。对于一个数x,如果a(n)<x<a(n+1),那么b(x-n) = x。
[解决办法]
本来就是一个简单的数学题目,数据分类如下:4个b,1个a依次循环,第100个b,之前有24个a,因此结果为100+24=124
[解决办法]
直接用乘除法,显然复杂度是常数
b(n)=n+(n-1)/4 应该就是这样了
[解决办法]