有 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 给出一个时间复杂度为O(logk)的解法，并给出代码

这个问题的解法可以用矩阵快速幂的方法来解决，具体的代码如下：long long matrix_fast_power(long long N, long long K, long long D)
{
long long ans = 0;
long long A[2][2] = {1, 0, D, 1}; // 二阶矩阵
long long result[2][2] = {1, 0, 0, 1}; // 单位矩阵
while(K)
{
if(K & 1)
{
// 矩阵乘法
long long temp[2][2] = {0};
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
for (int k = 0; k < 2; k++)
{
temp[i][j] += result[i][k] * A[k][j];
}
temp[i][j] %= N; // 将每个元素都限制在N范围内
}
}
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
result[i][j] = temp[i][j];
}
}
}
// 矩阵乘法
long long temp[2][2] = {0};
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
for (int k = 0; k < 2; k++)
{
temp[i][j] += A[i][k] * A[k][j];
}
temp[i][j] %= N; // 将每个元素都限制在N范围内
}
}
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
A[i][j] = temp[i][j];
}
}
K >>= 1;
}
ans = result[1][0]; // 结果
return ans;
}