有 N个方块，索引为 0到 (N-1)排列在一条线上。Snuke将通过以下程序来标记每个方格。 标记方格 0. 重复以下步骤N-1次。 初始化一个变量 x有 (A+D)modN，其中 A是上次标记的方块的索引。 当方格 x被标记，重复将 替换为 (x+1)modN。 标记方格 x. 找出Snuke第K次标记的广场的索引。 给出 T个测试案例，找出每个案例的答案。 N,K,D<=10^9 T<=10^5 给出一个时间复杂度是O(TlogK)的算法，并给出代码

要找出Snuke第K次标记的方格的索引，可以使用O(TlogK)时间复杂度的算法。算法的步骤如下： 1. 将K转换为二进制形式，记为B，其中B的长度为logK。
2. 用一个变量x来存储结果，x的初始值为0。
3. 对B中的每一位，计算x=(x+D)mod N，如果B中该位为1，则x=(x+A)mod N。
4. 返回x作为结果。以Python代码实现如下：def findIndex(N, A, D, K):
B = bin(K)[2:] #将K转换为二进制形式
x = 0
for ch in B:
x = (x+D) % N
if ch == "1":
x = (x+A) % N
return x

相关问题

有 N个方块，索引为 0到 (N-1)排列在一条线上。Snuke将通过以下程序来标记每个方格。 标记方格 0. 重复以下步骤i - iii (N-1)次。 初始化一个变量 x有 (A+D)modN，其中 A是上次标记的方块的索引。 当方格 x被标记，重复将 替换为 (x+1)modN。 标记方格 x. 找出Snuke第K次标记的广场的索引。 给出 T个测试案例，找出每个案例的答案。 N,K,D最大均为10^9，给出一个时间复杂度不超时的算法

由于N，K，D的最大值都为10^9，推荐使用高效的循环移位算法来解决这个问题。首先令x=A，令r=0，令m=1，令t=1，令y=0，令z=K；令i=0，令j=1，令k=0；然后，当i<N时，执行以下操作：r=r+m*t，m=m*D，t=t*D，x=x+y，y=y+z，i=i+1，j=j+1，k=k+1，当k=K时，输出索引i。最后，输出索引i即可得到Snuke第K次标记的方格的索引。