题目描述
暑假开始了，夏令营的日子也来临了。住进宿舍的第一天晚上，小A和新认识的同学们在宿舍里玩起了转圈游戏。编号为0n-1的n个小伙伴围成一圈，他们坐的位置也被编号为了0n-1。最初，第0号小伙伴在第0号位置，第1号小伙伴在第1号位置…依此类推。
游戏规则如下：每一轮第0号位置上的小伙伴顺时针走到第m号位置，第1号位置小伙伴走到第m+1号位置…依此类推，第n−m号位置上的小伙伴走到第0号位置，第n-m+1 号位置上的小伙伴走到第1号位置…第n-1号位置上的小伙伴顺时针走到第m-1号位置。
这个游戏实在太好玩了，以至于小A和他的小伙伴们玩了10^k轮，请问x号小伙伴最后走到了第几号位置。
输入
第一行有四个由单个空格分隔的整数n,m,k,x，意义如题所示。
输出
仅一行一个整数，表示10^k轮后第x号小伙伴的最终位置编号。
样例输入 Copy
10 3 4 5
样例输出 Copy
5
提示
对于30%的数据，0 < k < 7；
对于80%的数据，0 < k < 10^7；
对于100%的数据，1 <n < 1,000,000，0 < m < n，0 ≤ x < n，0 < k < 10^9
式子不难推导
（ x+ m10k ）%n
=(x%n+m%n10k%n)%n
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma comment(linker, "/stack:200000000") #pragma GCC optimize (2) #pragma G++ optimize (2) #include <bits/stdc++.h> #include <algorithm> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define wuyt main typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll inf = 1e15; const int maxn = 1e6 + 7; const int mod = 1e9 + 7; ll n,m,k,x; ll superpow(ll a,ll b){ ll ans=1; while (a>0) { if (a%2) ans=ans*b%n; b=b%n*b%n; a/=2; } return ans; } int main(){ n=read,m=read,k=read,x=read; ll res=superpow(k,10); res*=m; res%=n; res+=x; res%=n; cout<<res<<endl; return 0; }
