题目:
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 号位置.
思路:
当走的次数是 n 和 m 的最小公倍数的时候, 就会返回到最初的状态.
1. 设 n 和 m 的最小公倍数为 tmp
2. 对 10k 运用快速幂求解, 求解的过程中对 tmp 取余结果为 ans
3. 结果就是 m 乘以 ans 对 n 取余加上 x
代码:
- #include <bits/stdc++.h>
- #include <cmath>
- #define inf 0x3f3f3f3f
- #define FRE() freopen("in.txt", "r", stdin)
- #define FRO() freopen("out.txt", "w", stdout)
- using namespace std;
- typedef long long ll;
- ll MyMul(ll k, ll x, ll mod)
- {
- ll res = 1;
- x = x % mod;
- while(k)
- {
- if(k & 1)
- res = (res*x)%mod;
- k>>= 1;
- x = (x*x)%mod;
- }
- return res % mod;
- }
- int main()
- {
- ll n,m,k,x;
- cin>>n>>m>>k>>x;
- ll tmp = (n*m)/__gcd(n,m);
- cout<<(MyMul(k,10,tmp)*m+x)%n<<endl;
- return 0;
- }
转圈游戏(简单的快速幂)
来源: http://www.bubuko.com/infodetail-3172628.html