【AcWing】蓝桥杯集训每日一题Day24|快速幂|504.转圈游戏(C++)

504.转圈游戏

题目内容

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 号位置。
现在，一共进行了 10k 轮，请问 x 号小伙伴最后走到了第几号位置。

输入格式

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

输出格式

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

数据范围

1<n<10^6,
0<m<n,
1≤x≤n,
0<k<10^9

输入样例：

10 3 4 5

输出样例：

5

题目解析

n个人围成一圈，编号0~n-1，顺时针

每一轮相当于每个小朋友顺时针走m步
一共进行了$10^k$轮
初始在x位置的人最后在第几号位置

每一轮每个人顺时针走m个位置，经过$10^k$轮的话，一共会顺时针走$10^k\ast m$步
由于整个路径是个首尾相接的圆
当走到第n-1个位置的时候，再往下走一步就到了0的位置，所以最终的位置编号再mod一个n

k的数比较大，如果直接模拟，如果一个一个乘的话，要乘k次，一定会超时

如何优化

经典的求 $a^b模p$ 的结果
有一个标准模板，快速幂
类似于倍增和反复平方法
可以把复杂度做到$\log b$

先用模板求一下10的k次方模n的结果

通过公式变化式子

$$(x+10^k\ast m)MODp=xMODp+10^k\ast mMODp$$
$$=xMODp+10^{k}MODp\ast mMODp$$
取模可以往中间取，每一步都取个模，防止爆int

代码

#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;
	//当b不为0的时候
	while (b)
	{
		//如果发现b的个位是1
		if (b & 1) res = (LL)res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

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

	return 0;
}