Acwing.504 转圈游戏(带取余的快速幂)

题目

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号位置。

现在，一共进行了 10k轮，请问 x号小伙伴最后走到了第几号位置。

输入格式

输入共 1行，包含 4个整数 n、m、k、x，每两个整数之间用一个空格隔开。

输出格式

输出共 1行，包含 1个整数，表示 10k轮后 x号小伙伴所在的位置编号。

数据范围

1<n<106

0<m<n

1≤x≤n

0<k<109

输入样例：

10 3 4 5

输出样例：

5

题解

import java.util.Scanner;/*** @author akuya* @create 2024-04-05-11:11*/
public class CircleGame {static int n,m,k,x;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);n=scanner.nextInt();m=scanner.nextInt();k=scanner.nextInt();x=scanner.nextInt();long num=quick(10,k);num=(x+(num*m))%n;System.out.println(num%n);}public static long quick(long a,int s){long ans=1;while(s!=0) {if ((s & 1) != 0) {ans = (ans * a) % n;}a = (a*a)%n;s >>= 1;}return ans;}
}

思路

这道题没有任何思路可言，相信大家都能看出这只是一道数据较大的小学数学题，那么，我们需要懂的就只有如何使用快速幂，并且在快速幂中进行取余。大家看代码模板即可。