Java实现 蓝桥杯 算法提高 转圈游戏(暴力快速幂)java南 墙-

试题 算法提高 转圈游戏

问题描述
　　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 号小伙伴所在的位置编号。
样例输入
10 3 4 5
样例输出
5
数据规模和约定
　　对于 30%的数据,0 < k < 7;
　　对于 80%的数据,0 < k < 107;
　　对于 100%的数据,1 < n < 1,000,000,0 < m < n,1 ≤ x ≤ n,0 < k < 109。

   这个题的意思，就是             x+m*10^k%n         从x开始每次向后走m次，一共走10的k次方在%n，因为只有n个人，大于n就从头开始             这里肯定会超时的，所以，我们要是求10的k次方怎么办，这里我们举一个小例子，2的20倍是多少             正常2*2*2*2…………*2             我们这里使用 ((((2)*2+1)*2)*2)   这样也是2的20倍             +1是因为我们这里出现了一个奇数 

import java.util.Scanner; public class Main { public static void main(String[] args) {         Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int k = sc.nextInt(); int x = sc.nextInt(); int count = counting(10, k, n); int result = (x + m * count) % n;         System.out.print(result); } public static int counting(int cur_temp, int cur_count, int max_list) { int sum_num = 1; int cur_num = cur_temp; while (cur_count != 0) { if ((cur_count & 1) != 0) {//如果是奇数的话，证明我要乘一个单个的                 sum_num = sum_num * cur_num; }             cur_num = (cur_num * cur_num) % max_list;             cur_count = cur_count >> 1;             sum_num = sum_num % max_list; } return sum_num; } }