快速幂

• 用处
• 模板题
• 【题目描述】
• 【输入格式】
• 【输出格式】
• 样例
• 样例输入
• 样例输出
• 样例说明
• 数据范围与提示
• 解析
• 练习题 NOIP2013提高组day1【转圈游戏】
• 题目描述
• 输入格式
• 输出格式
• 样例
• 样例输入1
• 样例输出1
• 数据范围与提示

用处

一个能快速求$n^{k}\%p$的算法，在数论题目里可以用来模拟多次重复的运算，是数论的基础算法。

模板题

【题目描述】

求$n^{k}\%p$的值。

【输入格式】

一行，包含三个数$n,k,p$

【输出格式】

一行，输出$n^{k}\%p$的值。

样例

样例输入

2 6 23

样例输出

18

样例说明

$2^{6}=64,64\%23=18$

数据范围与提示

对于全部数据，$1le n,kle 10^{15},1 leq p leq 10^{9}$

解析

这是一道基本的数论题，不用数论算法就会超时（简单来说，不用数论思想就是暴力模拟）。
暴力模拟的时间复杂度为$O(k),$但$k$最大可以取$10^{15},$肯定会超时。
快速幂是一种时间复杂度为$O(log2(k))$的算法，这代表$k$甚至可以取到$LARGE2^{ ormalsize2 imes10^{8}}(2^{200000000})$。
可以说是无限了，C++中很难有这样的时间和内存够这种数运算了$(FFT$也做不到呀$)$。
为什么说快速幂时间复杂度为为$O(log2(k)),$这因为它的算法模式。
利用$2$进制来分治，将运算次数缩小到二分的次数。
比如数据

2 29 657

$n=2,k=29,p=657$
将$k$转化成$2$进制得$11101,ans=1$
每次$n$都会平方并进行取模，然后将$k div 2$
因为$n^{k}=(n imes2)^{k div 2}$
但是$C$语言中默认向下取整，所以$5div 2=2,$但是还有个$1$该怎么办呢？
所以为什么转化为$2$进制，当$k\%2=1,$代表有一个$1$是多出来的，要先把这$1$个$a$先乘上。
具体代码实现如下 #include #include using namespace std; int n,k,p; int ksm(int a,int b,int inf) { int ans=1;a%=inf; while(b) { if(b&1/*b%2==1*/)ans=ans*a%inf; a=a*a%inf;b>>=1;/*b=b/2;*/ } return 0; } int main() { scanf("%d%d%d",&n,&k,&p); printf("%d ",ksm(n,k,p)); }

练习题 NOIP2013提高组day1【转圈游戏】

题目描述

$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$号小伙伴所在的位置编号。

样例

样例输入1

10 3 4 5

样例输出1

5

数据范围与提示

对于$30\%$的数据$,0 < k < 7；$
对于$80\%$的数据$,0 < k < 10^{7};$
对于$100\%$的数据$,1 < n < 10^{6},0 < m < n,1 leq x leq n,0 < k < 10^9。$