信息学奥赛一本通 1617：转圈游戏 | 1875：【13NOIP提高组】转圈游戏 | 洛谷 P1965 [NOIP2013 提高组] 转圈游戏

【题目链接】

ybt 1617：转圈游戏
ybt 1875：【13NOIP提高组】转圈游戏
洛谷 P1965 [NOIP2013 提高组] 转圈游戏

【题目考点】

1. 取模运算

【解题思路】

第x号小伙伴第一轮后走到$x+m$位置，第二轮后走到$x+2m$位置，如果该位置的值超过了n，位置编号要减n，使得位置编号只能在0~n-1范围内。因此$10^k$轮后，第x号小伙伴所在的位置为$(x+10^k\cdot m)\%n$。
已知x、m都小于n。根据同余定理的乘法应用：$a\cdot b\%m=(a\%m\cdot b\%m)\%m$
有：
$(x+10^k\cdot m)\%n$
$=(x\%n+(10^k\%n\cdot m\%n)\%n)\%n$
$=(x+(10^k\%n\cdot m)\%n)\%n$
主要问题是求$10^k\%n$
k达到$10^9$，这里必须使用快速幂算法（快速幂算法求幂的复杂度为$O(logn)$，n是指数的大小）。
根据同余定理，有：$a^b\%m=(a\%m{)}^b$。在使用快速幂的过程中，对于底数a和结果r，每次运算后都对m取模即可。

【题解代码】

解法1：快速幂

#include
using namespace std;
int fastPowMod(int a, int b, int m)//快速幂求a^b%m
{	
	int r = 1;//结果
	while(b > 0)
	{
		if(b % 2 == 1)
			r = (r * a) % m;
		a = (a * a) % m;
		b /= 2;
	} 
	return r;
}
int main()
{
	int n, m, k, x;
	cin >> n >> m >> k >> x;
	cout << (x + fastPowMod(10, k, n) * m % n) % n;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21