P8671 [蓝桥杯 2018 国 AC] 约瑟夫环 题解

· · 题解

思路

第一眼：直接把 P1996 约瑟夫问题 的代码稍微调一下就好。

这种方法显然要超时，因为这种写法的复杂度为 O(nk)，只能过 3 个点。有没有更好的方法呢？有，那就是递推式法。

我们可以推出这个递推式，现在复杂度降为了 O(n)：

f(n) =(f(n-1) + k)\mod n

具体证明可以借鉴这篇文章。

Python Code：

n, k = map(int, input().split())
s = 0
for i in range(2, n+1): #从2开始循环
    s = (s+k) % i #递推式
print(s+1) #f(0)为1,所以要加上1

AC记录，供参考