原本我是在word文档上写这种东西的，在杨老师的“强迫”下，我开始写了博客。
这是我在博客上的第一天，就先来个简单的，下面请看题：
|
试题描述
|
|
有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号位置。 现在，一共进行了10^k 轮，请问x号小伙伴最后走到了第几号位置。 |
|
输入
|
|
输入共1行，包含4个整数n、m、k、x，每两个整数之间用一个空格隔开。
|
|
输出
|
|
输出共1行，包含1个整数，表示10^k轮后x号小伙伴所在的位置编号。
|
|
输入示例
|
|
10 3 4 5
|
|
输出示例
|
|
5
|
|
其他说明
|
|
数据范围：0<n<10^6,0<m<n,0<x<=n,0<k<10^9
|
题目看起来比较简单。最终解应该就是(x+n*10^k)%n。如果这都想不到的话，那就没救了。
其他都好处理关键是这个10^k怎么处理，数据范围中0<k<10^9,如果真一个一个往上乘以10的话肯定没戏。
怎么办呢，有一个高级的东西叫做快速幂。
第一次听说是初二时寒假上课杨老师讲的，但是早就忘光了。今天重新复习了一遍。
快速幂有两种方法，先说一种比较简单理解的，递归法
我们要求的是x^n，由于乘法公式,当n为偶数时原式可化为x^n=(x*x)^(n/2)，这样递归就转为了当n/2的情况。当n为奇数时就是x^n=(x*x)^(n/2)*x，也同样可以转化，这样的话，n每次减半，时间复杂度为O(log 2 (n)),代码在下面。
typedef long long LL;
LL mod_pow2(LL x,LL n,LL m)
{
if(n==) return ;
LL ans=mod_pow2(x*x,n/,m);
if(n&)ans=ans*x%m;
return ans;
}
还有一种方法，是基于n的二进制数的。假设n=2^k,则可以表示为x^n=x^2^2^…^2,这样我们做简单的k次平方运算就可以求出x^n的值了。
把问题转为一般化，若n!=2^k,将n转化为一些2次方的和，n=2^k2+2^k2+…，每个数都能完成这样的操作，因为这其实就是二进制。
知道上面的，既可以轻易的得出x^n=x^2^k1*x^2^k2*……
举个例子22的二进制数是10110，那么x^22=x^16*x^4*x^2.这些16,4,2的数其实就是22的二进制数上1所对应的数值。
代码送上：
typedef long long LL;
LL mod_pow1(LL x,LL n,LL m)
{
LL ans=;//计算总和
while(n>)
{
if(n&)ans=ans*x%m;//n&1的意思是n的二进制最后一位是否等于1
x=x*x%m;
n>>=;//n的二进制数整体向右移一位
}
return ans%m;
}
将快速幂复习后，这道题简直是水到家了，代码就不写了。
第一次写博客，写的比较渣，好多地方语言表达不妥当，看着以后进步吧。
还有下回我管老师要一个数学公式编辑器，网上的需要花钱，等有了公式编辑器写数学推导就舒服多了。