新手光能
3866 转圈游戏
题目描述 Description
有n头奶牛住在n个环形的牛圈，奶牛编号为0到n-1，牛圈编号也为0到n-1，i号牛住在第i号牛圈。
现在牛们想实施住宅滚动制度。每滚动一次，第0号圈的奶牛会顺时针搬到第m号牛圈中，第1号圈的奶牛会顺时针搬到第1+m号牛圈中，...，第n-m号圈的奶牛会顺时针搬到0号牛圈，也就是说原来的第i号牛圈的奶牛会顺时针搬到i+m号牛圈。
试判断，进行了10^k轮滚动后，原来在x号圈的奶牛现在在几号牛圈。
输入描述 Input Description
一行，四个正整数，n m k x
输出描述 Output Description
10^k轮后，最初在第x个圈的奶牛所处牛圈的编号
样例输入 Sample Input
10 3 4 5
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
对于 30%的数据，0 < k < 7；
对于 80%的数据，0 < k < 10^7；
对于 100%的数据，1 < n < 1,000,000，0 < m < n，1 <= x <=n，0 < k < 10^9。
求代码
资深守护
分治-快速幂
long long p(int q,int u)
{
if(q==0)return 1;
if(q==1)return 10;
long long r=p(q/2,u);
return (r*r*p(q%2,u))%u;
}
计算10的q次方除以u的余数
原理：a^k%b=((a^(k/2)%b)^2*a^(k%2))%b
时间复杂度O(log2 k)
高级光能
1.递归（快速幂）return每次运算%n（防止超long long）
2.主函数，循环次数 qs(10, k)次//我的函数是qs，你的可能不一样
x=(x+m)%n;//+m:每次转圈加的，%n:保证在总个数以内
初级天翼
1
