洛谷:P1965
OJ:P5972
纯模拟,90分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | /**************************************************************** * Description: 2013年提高组第一题 转圈游戏 90分 * Author: Alex Li * Date: 2024-10-11 12:04:53 * LastEditTime: 2024-10-11 12:08:18 ****************************************************************/ #include <iostream> using namespace std; int n, m, k, x; int a[1000005]; int main(){ // 读取输入的四个整数 n、m、k、x cin >> n >> m >> k >> x; int i; a[0] = x; // 记录初始位置 // 模拟小伙伴的位置变化,直到出现循环 for (i = 1;; i++) { x += m; // 小伙伴向前移动 m 个位置 if (x >= n) // 如果超过了最大位置编号,循环回到起点 x -= n; a[i] = x; // 记录当前位置 if (x == a[0]) // 如果当前位置等于初始位置,说明出现循环 break; } int q = 1; // 计算 q = (10^k) % i,其中 i 是循环节的长度 for (int j = 1; j <= k; j++) q = q * 10 % i; // 输出经过 10k 轮后 x 号小伙伴所在的位置 cout << a[q] << endl; return 0; } |
快速幂: 100分
根据模运算的的分配率可以得到 (x%n+m%n*10k%n)%n只需用快速幂求出10k
mod_pow
:
long long
类型:防止数值过大导致的溢出。mod_pow(10, k, n)
,得到 power_mod
。final_position
,即编号为 x 的小伙伴经过 10k 轮后所在的位置。代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | /**************************************************************** * Description: 2013年提高组第一题 转圈游戏 100分 * Author: Alex Li * Date: 2024-10-11 12:07:57 * LastEditTime: 2024-10-11 12:08:08 ****************************************************************/ #include <iostream> using namespace std; #define LL long long // 快速幂取模函数,计算 (base^exponent) % mod LL mod_pow(LL base, LL exponent, LL mod) { LL result = 1; // 初始化结果为1 base %= mod; // 先取模,防止base过大 while (exponent > 0) { // 如果当前指数位是1,则将结果乘以base if (exponent & 1) result = result * base % mod; // base自乘,指数右移一位 base = base * base % mod; exponent >>= 1; } return result; } int main() { freopen("circle.in","r",stdin); freopen("circle.out","w",stdout); // 定义变量,使用long long防止溢出 LL n, m, k, x; cin >> n >> m >> k >> x; // 计算 (10^k) % n,使用快速幂取模 LL power_mod = mod_pow(10, k, n); // 计算最终位置 // final_position = (x + m * (10^k % n)) % n LL final_position = (x % n + (m % n) * power_mod % n) % n; // 输出结果 cout << final_position << endl; return 0; } |