转圈游戏（acwing）

题目描述：

n 个小伙伴（编号从 0 到 n−1）围坐一圈玩游戏。

按照顺时针方向给 n 个位置编号，从 0 到 n−1。

最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，…，依此类推。 

游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第 m+1 号位置，…，依此类推，第 n−m 号位置上的小伙伴走到第 0 号位置，第 n−m+1 号位置上的小伙伴走到第 1 号位置，…，第 n−1 号位置上的小伙伴顺时针走到第 m−1 号位置。

现在，一共进行了 10^k 轮，请问 x 号小伙伴最后走到了第几号位置。

输入格式：

输入共 1 行，包含 4 个整数 n、m、k、x，每两个整数之间用一个空格隔开。

输出格式：

输出共 1 行，包含 1 个整数，表示 10^k 轮后 x 号小伙伴所在的位置编号。

数据范围：

1<n<1e6
0<m<n,
1≤x≤n,
0<k<1e9

输入样例：

10 3 4 5

输出样例：

5

分析步骤：

  第一：我们拿到这道题目，知道了数据范围后，就应该想到如果用for循环暴力硬解的话一定会超时。我们仔细看看题目，我们要求的是向后走很多轮我们现在应该在第几号位置并且每经过n个位置的时候，对n取模。想到这里有没有发现这个题目和我们的快速幂的思想很像，我们可以先用快速幂算法去求出走了多远，在把走的路程加上初始的位置就可以确定我们现在处于哪个位置了。

  第二：书写主函数，构建整体框架：

• 定义我们的值，并且输入进去

• 再根据我们的思路，先求出走过的距离+初始的位置就可以得出我们最终的位置

int main()
{
    int n, m, k, x;
    scanf("%d%d%d%d", &n, &m, &k, &x);
 
    printf("%d\n", (x + qmi(10, k, n) * (LL)m) % n);
    return 0;
}

第三： 书写快速幂：

• 这个快速幂是个模板，大家记住就行，大家如果看不懂的话可以去B站看看讲解。

int qmi(int a, int b, int p)
{
    int res = 1 % p;
    while (b)
    {
        if (b & 1) res = res * (LL)a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}

代码：

 
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
typedef long long LL;
 
int qmi(int a, int b, int p)
{
    int res = 1 % p;
    while (b)
    {
        if (b & 1) res = res * (LL)a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}
 
int main()
{
    int n, m, k, x;
    scanf("%d%d%d%d", &n, &m, &k, &x);
 
    printf("%d\n", (x + qmi(10, k, n) * (LL)m) % n);
    return 0;
}