1283: 转圈游戏

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:25 通过:7

题目描述

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号小伙伴最后走到了第几号位置。

输入格式

共一行,包含四个整数n,m,k,x,每两个整数之间用一个空格隔开。

输出格式

一个整数,表示10^k轮后x号小伙伴所在的位置编号。

输入样例 复制

10 3 4 5

输出样例 复制

5

数据范围与提示

注意数据范围和时间限制
说明/提示
对于30%的数据,0<k<7;
对于80%的数据,0<k<10^7
对于100%的数据,1<n<10^6,0<m<n,1<x≤n,0<k<10^9
若m=x*y则m%n等价于(x%n*y%n)%n,即最终取余可以通过每步取余来实现,这样可以避免数据范围超限
10^11=10^10*10=(10^5)^2*10=((10^2)^2*10)^2*10=10^8*10^2*10^1


分类标签