[NOIP2013 提高组] 转圈游戏
个小伙伴(编号从 到 )围坐一圈玩游戏。按照顺时针方向给 个位置编号,从 到 。最初,第 号小伙伴在第 号位置,第 号小伙伴在第 号位置,……,依此类推。游戏规则如下:每一轮第 号位置上的小伙伴顺时针走到第 号位置,第 号位置小伙伴走到第 号位置,……,依此类推,第 号位置上的小伙伴走到第 号位置,第 号位置上的小伙伴走到第 号位置,……,第 号位置上的小伙伴顺时针走到第 号位置。
现在,一共进行了 轮,请问 号小伙伴最后走到了第几号位置。
对于 的数据,,,,。
解法:
相当于 号小伙伴每次在圆环上向前走了 步,走了 步
则可以推出式子:
代码:
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int LOG = 50;
int n,m,k,x;
int id;
int jump[LOG];
int qpow(int num,int x){
int ans = 1,res = num;
while(x){
if(x & 1) ans = ans * res % n;
x >>= 1,res = res * res % n;
}
return ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m>>k>>x;
cout<<(x +(m * qpow(10,k)) % n) % n;
return 0;
}