Description

?n個MM（編號從0到n-1）圍在一圈“丟手絹”。按照順時針方向給n個位置編號，從0到n-1。最初，第0號MM在第0號位置，第1號MM在第1號位置，……，依此類推。?

游戲規則如下：每一輪第0號位置上的MM順時針走到第m號位置，第1號位置MM走到第m+1號位置，……，依此類推，第n?m號位置上的MM走到第0號位置，第n-m+1號位置上的MM走到第1號位置，……，第n-1號位置上的MM順時針走到第m-1號位置。??現在，一共進行了10^k輪，請問x號MM最后走到了第幾號位置。??

Input

輸入共1行，包含4個整數n、m、k、x，每兩個整數之間用一個空格隔開。?

Output

輸出共1行，包含1個整數，表示10^k輪后x號MM所在的位置編號。??

Sample Input

10 3 4 5

Sample Output

5

Hint

對于30%的數據，0<?<7；?對于80%的數據，0<?<10^7；?

對于100%的數據，1<?<1,000,000，0<?<?，0≤x?<n< span="">，0<?<10^9。?

#include <cstdio> #include <iostream> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <queue> #include <vector> #include <map> using namespace std;#define ll long long #define eps 1e-9const int inf = 0x3f3f3f3f; const int mod = 1e9+7;ll qsm(ll a, ll b, ll c) {ll sum = 1;a = a % c;while(b){if(b & 1)sum = (sum * a) % c;b /= 2;a = (a * a) % c;}return sum; }int main() {ll n, m, k, x;scanf("%lld%lld%lld%lld", &n, &m, &k, &x);ll buffer = qsm(10, k, n);ll s = ((x % n) + ((m % n) * buffer) % n) % n;printf("%lld\n", s);return 0; }

?

轉載于:https://www.cnblogs.com/RootVount/p/11340435.html

總結

以上是生活随笔為你收集整理的SDNU 1300.转圈游戏（快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。