老火装饰网,濠江岁月演员表,n0684
幂运算：\(x ^ n\)
根据其一般定义我们可以简单实现其非负整数情况下的函数
定义法：
我要评论int pow (int x, int n) {
int result = 1;
while(n--) {
result *= x;
}
return result;
}
不难看出此时算法的时间复杂度是\(o(n)\)，一旦n取较大数值，计算时间就会大大增加，极其容易出现超时的情况。
快速幂：
首先要在此列举两个前提：
计算机是通过二进制进行存储数据的，对二进制数据可以直接进行操作。
\(2^n+2^n=2*2^n=2^{n + 1}\)
对于\(x ^ n\)，其中n可以表示为m位的二进制形式，即\(n=n_12^0+n_22^1+n_32^3+\cdots+n_m2^{m-1}\)
那么\(x ^ n=x ^ {n_12^0+n_22^1+n_32^3+\cdots+n_m2^{m-1}}\)
即\(x^n=x ^ {n_12^0}x^{n_22^1}x^{n_32^3}\cdots x^{n_m2^{m-1}}\)
根据前提1，计算机可以直接对二进制格式存储的数据进行读取，那么我们就可以对\(n\)一个个读取再对其进行累乘。
当取到第\(a\)位时，其乘数有通项公式：\(x^{n_a2^{a-1}}\)
通过标准库math，用代码实现：
int pow (int x, int n) {
int result = 1;
int a = 1;
while(n) {
if(n & 1) result *= round( pow(x, 1 << (a - 1)) );//round的作用在于double转int时防止丢失精度，对1进行位运算是一种计算2的n次幂的快速方法
n >>= 1;
a++;
}
return result;
}
但实际上这个调用了标准库的代码并没有实现快速幂，因为仍然是采用pow()进行的运算
此处由 \(2^n+2^n=2\times2^n=2^{n + 1}\)
即\((x ^ {2 ^ {n}} )^2=x ^ {2\times 2 ^ {n}} =x ^ {2 ^ {n + 1}}\)
因此我们可以通过对前项进行二次幂运算得到后项
先得到首项\(f(1)=x^{2^{1-1}}=x\)
即令int f = x
具体实现：
int pow (int x, int n) {
int result = 1;
int f = x;
while(n) {
if(n & 1) result *= f;
f *= f;
n >>= 1;
}
return result;
}
不难发现此时算法的时间复杂度由其次数的二进制位数而决定，即\(o(m)\)也就是\(o([log_2n+1]-1)\)
另外因为此算法常常用于计算大数，所以int类型最好都换成long long类型，防止溢出。
对\(x^n\)取模运算：\(x^n％p\)，当n极大时，同样其运算量也会增大
这就需要我们寻求一种快速解决的方法，此时可以运用我们上文所提到的快速幂算法
引论：\((m*n)％p=((m％p)(n％p))％p\)
证明如下：令\(\left\{ \begin{array}{c} m=(ip+c)& (i\in\mathbb{z} )\\ n=(jp+d) & (j\in\mathbb{z} )\end{array} \right.\)
则有\(\left\{ \begin{array}{c} m％p=c\\ n％p=d \end{array} \right.\)
原式\((m*n)％p\\=((ip+c)(jp+d))％p\\=(jip^2+jpc+ipd+cd)％p\\=(jip^2+jpc+ipd+cd)％p\\=((jip+jc+id)p+cd)％p\)
引论2：\((np+a)％p=a％p\quad (n\in\mathbb{z} )\)
证明如下：设\(f(n,p,a)=(np+a)％p\quad (n\in\mathbb{z} )\)
则由定义有\((np+a)％p=\frac{np+d}{p}-\{[\frac{np+d}{p}+1]-1\}\\ =d-p\{[\frac{d}{p}+1]-1\}\)
显而易见，\((np+a)％p=a\)与\(n\)无关
令\(n=0\)得\((np+a)％p=a％p\quad (n\in\mathbb{z} )\\ q.e.d\)
\(=(cd)％p\\=((m％p)(n％p))％p\)
即\((m*n)％p=((m％p)(n％p))％p\\ q.e.d\)
因此对于\(x^n％p\)
可以写成\((x ^ {n_12^0}x^{n_22^1}x^{n_32^3}\cdots x^{n_m2^{m-1}})％p\\ =((x ^ {n_12^0}％p)(x^{n_22^1}％p)(x^{n_32^3}％p)\cdots (x^{n_m2^{m-1}}％p))％p\)
并且由之前的推定\((x ^ {2 ^ {n}} )^2=x ^ {2\times 2 ^ {n}} =x ^ {2 ^ {n + 1}}\)
有\((x ^ {2 ^ {n}} ％p)^2％p =(x ^ {2 ^ {n}})^2％p=x ^ {2 ^ {n + 1}}％p\)
代码实现：
int mod (int x, int n, int p) {
int result = 1;
int f = x % p;
while(n) {
if(n & 1) result = (result * f)%p;
f = (f * f)%p;
n >>= 1;
}
return result;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论