网站建设q-9,app开发公司哪家比较好,俱乐部手机网站模板,企业网站展示生产的处方药介绍处罚案件问题描述 n个小伙伴#xff08;编号从0到n-1#xff09;围坐一圈玩游戏。按照顺时针方向给n个位置编号#xff0c;从0到n-1。 最初#xff0c;第0号小伙伴在第0号位置#xff0c;第1号小伙伴在第 1 号位置#xff0c;……#xff0c;依此类推。 游戏规则如下编号从0到n-1围坐一圈玩游戏。按照顺时针方向给n个位置编号从0到n-1。 最初第0号小伙伴在第0号位置第1号小伙伴在第 1 号位置……依此类推。 游戏规则如下每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置第 1 号位置小伙伴走到第m1号位置……依此类推第n−m号位置上的小伙伴走到第0号位置第n-m1 号位置上的小伙伴走到第1号位置……第 n-1 号位置上的小伙伴顺时针走到第m-1号位置。 现在一共进行了10的k次方轮请问x号小伙伴最后走到了第几号位置。
输入格式 输入共1行包含 4个整数n、m、k、x每两个整数之间用一个空格隔开。
输出格式 输出共1行包含 1个整数表示10的k次方轮后x号小伙伴所在的位置编号。
样例输入
10 3 4 5
样例输出
5
数据规模和约定 1n100000 0mn 0xn 0k1000000000。
#includeiostream
using namespace std;long long quick(long long num, long long k, long long n) {long long ans 1;while (k 0) {if (k % 2 1) {ans ans * num % n % n;}num num * num % n;k / 2;}return ans % n;
}int main() {long long n, m, k, x;cin n m k x;m % n;cout (x m * quick(10, k, n)) % n;return 0;
}
总结
核心是化简10的k次
然后答案就是x移动10的k次个m然后对n取余
运用快速幂的思想
如果指数为奇数就把指数-1然后ans乘以一个底数也就是10
如果指数为偶数就把质数缩小一半然后底数平方即num*num
