一.问题描述
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 号位置。
现在,一共进行了1e4轮,请问 x 号小伙伴最后走到了第几号位置。
二.设计思路
他们围成一个圈,走第一轮, x 会走到 x + m%n 号,走第二轮, x 会走到 x + 2 * m%n 号,以此类推,第10的k次方,会走到 x + 10^k * m%n。难点就在于求10的k次方。
所以我们写一个快速幂的函数
三.流程图
四.伪代码
1
五.代码实现
快速幂
1LL pow_mod(LL a, LL b){
LL res = 1;
while(b > 0){
if(b & 1){
res = res * a % n;
}
a = a * a % n;
b >>= 1;
}
return res;
}
代码
#include<bits/stdc++.h>
using namespace std;
int n, m, k, x;
typedef long long LL;
LL pow_mod(LL a, LL b){
LL res = 1;
while(b > 0){
if(b & 1){
res = res * a % n;
}
a = a * a % n;
b >>= 1;
}
return res;
}
int main(){
cin >> n >> m >> k >> x;
cout << (x + pow_mod(10, k) * m % n) % n;
return 0;
}
标签:m%,走到,位置,res,每日,小伙伴,打卡,LL From: https://www.cnblogs.com/leapssisbird/p/17331106.html