NYOJ 102 次方求模

谁借莪１个温暖的怀抱￠ 2022-08-25 01:50 155阅读 0赞

## 次方求模 ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 3

描述

求a的b次方对c取余的值

输入

第一行输入一个整数n表示测试数据的组数（n<100）  
每组测试只有一行，其中有三个正整数a,b,c(1=<a,b,c<=1000000000)

输出

输出a的b次方对c取余之后的结果

样例输入

3
    2 3 5
    3 100 10
    11 12345 12345

样例输出

3
    1
    10481

思路：根据模的性质来求 a\*b % c = ((a%c) \* (b%c)) % c ?

#include <stdio.h>
    
    int main()
    {
    	int m;
    	scanf("%d",&m);
    	while (m--)
    	{
    		int a,b,c;
    		int i,sum;
    		scanf("%d %d %d",&a,&b,&c);
    		sum = a;
    		for (i=1; i<b; i++)
    		{
    			sum = ((sum % c) * (a % c)) % c;
    		}
    		printf("%d\n",sum);
    	}
    	return 0;
    }

额。。。以上代码会超时。。。。

还好《算法导论》里面有介绍这样一种算法：反复平方法求数的幂。

设<bk,bk-1.....b1,b0>是b的二进制表示（即二进制表示有k+1位长，bk为最高有效位，b0为最低有效位）。随着c的值从0到b成倍增长，下列过程最终计算出 a^c mod n

MODULAR-EXPONENTIATION(a,b,n)

1 c = 0

2 d = 1

3 let<bk,bk-1,....b0>be the binary representation of b;

4 for i=k down to 0

5 c = 2c

6 d = (d\*d) mod n

7 if bi == 1

8 c = c+1

9 d = (d\*a)mod n

10 return d;

#include <stdio.h>
    
    int main()
    {
    	int m;
    	scanf("%d",&m);
    	while (m--)
    	{
    		long long a,b,c;
    		long long sum = 1;
    		scanf("%lld %lld %lld",&a,&b,&c);
    		while (b)
    		{
    			if (b % 2 == 1)
    			{
    				sum = (sum * a) % c;
    			}
    			b /= 2;
    			a = (a*a) % c;
    		}
    		printf("%lld\n",sum);
    	}
    	return 0;
    }

快速求幂算法。

快速求正整数次幂，当然不能直接死乘。举个例子：  
  
3 ^ 999 = 3 \* 3 \* 3 \* … \* 3  
  
直接乘要做998次乘法。但事实上可以这样做，先求出2^k次幂：  
  
3 ^ 2 = 3 \* 3  
3 ^ 4 = (3 ^ 2) \* (3 ^ 2)  
3 ^ 8 = (3 ^ 4) \* (3 ^ 4)  
3 ^ 16 = (3 ^ 8) \* (3 ^ 8)  
3 ^ 32 = (3 ^ 16) \* (3 ^ 16)  
3 ^ 64 = (3 ^ 32) \* (3 ^ 32)  
3 ^ 128 = (3 ^ 64) \* (3 ^ 64)  
3 ^ 256 = (3 ^ 128) \* (3 ^ 128)  
3 ^ 512 = (3 ^ 256) \* (3 ^ 256)  
  
再相乘：  
  
3 ^ 999  
= 3 ^ (512 + 256 + 128 + 64 + 32 + 4 + 2 + 1)  
= (3 ^ 512) \* (3 ^ 256) \* (3 ^ 128) \* (3 ^ 64) \* (3 ^ 32) \* (3 ^ 4) \* (3 ^ 2) \* 3  
  
这样只要做16次乘法。即使加上一些辅助的存储和运算，也比直接乘高效得多（尤其如果这里底数是成百上千位的大数字的话）。  
  
我们发现，把999转为2进制数：1111100111，其各位就是要乘的数。这提示我们利用求二进制位的算法（其中mod是模运算）：  
  
REVERSE\_BINARY(n)  
1 while (n > 0)  
2 do output (n mod 2)  
3 n ← n / 2  
  
这个算法给出正整数n的反向二制进位，如6就给出011（6的二进制表示为110）。事实上这个算法对任意的p进制数是通用的，只要把其中的2换成p就可以了。  
  
如何把它改编为求幂运算？我们发现这个算法是从低位向高位做的，而恰好我们求幂也想从低次幂向高次幂计算（参看前面的例子）。而且我们知道前面求出的每个2^k次幂只参与一次乘法运算，这就提示我们并不把所有的中间结果保存下来，而是在计算出它们后就立即运算。于是，我们要做的就是把输出语句改为要做的乘法运算，并在n减少的同时不断地累积求2^k次幂。  
  
还是看算法吧：  
  
POWER\_INTEGER(x, n)  
1 pow ← 1  
2 while (n > 0)  
3 do if (n mod 2 = 1)  
4 then pow ← pow \* x  
5 x ← x \* x  
6 n ← n / 2  
7 return pow  
  
不难看出这个算法与前面算法的关系。在第1步给出结果的初值1，在while循环内进行运算。3、4中的if语句就来自REVERSE\_BINARY的输出语句，不过改成了如果是1则向pow中乘。5句则是不断地计算x的2^k次幂，如对前面的例子就是计算2^2、2^4、2^8、…、2^512。  
  
应该指出，POWER\_INTEGER比前面分析的要再多做两次乘法，一次是向pow中第一次乘x，如2^1也要进行这个乘法；另一次则是在算法的最后，n除以2后该跳出循环，而前面一次x的自乘就浪费掉了（也可以考虑改变循环模式优化掉它）。另外，每趟while循环都要进行一次除法和一次模运算，这多数情况下除法和模运算都比乘法慢许多，不过好在我们往往可以用位运算来代替它。  
  
相应的C++代码如下  
  
NumberType pow\_n(NumberType x, unsigned int n)  
\{  
NumberType pw = 1;  
  
while (n > 0) \{  
if ((pw % 2) == 1)  
pw \*= x;  
x \*= x;  
n /= 2;  
  
\}  
  
return pw;  
\}  
  
进行简单的优化后则有：  
  
NumberType optimized\_pow\_n(NumberType x, unsigned int n)  
\{  
NumberType pw = 1;  
  
while (n > 0) \{  
if (n & 1) // n & 1 等价于 (n % 2) == 1  
pw \*= x;  
x \*= x;  
n >>= 1; // n >>= 1 等价于 n /= 2  
\}  
  
return pw;  
\}  
  
注1：快速求幂算法POWER\_INTEGER常被写成递归的形式，算法实质完全相同，但却是无必要的。  
  
注2：这个算法并不是做乘法数最少的，但多数情况下是足够快并且足够简单的。如果单纯追求做乘法数最少，则未必应该用2^k次幂进行计算。如果还允许做除法，则问题会进一步复杂化。  
  
如：  
  
x ^ 2 = x \* x  
x ^ 4 = (x ^ 2) \* (x ^ 2)  
x ^ 8 = (x ^ 4) \* (x ^ 4)  
x ^ 16 = (x ^ 8) \* (x ^ 8)  
x ^ 31 = (x ^ 16) \* (x ^ 8) \* (x ^ 4) \* (x ^ 2) \* x  
要8次乘法。  
  
x ^ 2 = x \* x  
x ^ 4 = (x ^ 2) \* (x ^ 2)  
x ^ 8 = (x ^ 4) \* (x ^ 4)  
x ^ 10 = (x ^ 8) \* (x ^ 2)  
x ^ 20 = (x ^ 10) \* (x ^ 10)  
x ^ 30 = (x ^ 20) \* (x ^ 10)  
x ^ 31 = (x ^ 30) \* x  
只要7次乘法。  
  
x ^ 2 = x \* x  
x ^ 4 = (x ^ 2) \* (x ^ 2)  
x ^ 8 = (x ^ 4) \* (x ^ 4)  
x ^ 16 = (x ^ 8) \* (x ^ 8)  
x ^ 32 = (x ^ 16) \* (x ^ 16)  
x ^ 31 = (x ^ 32) / x  
只要6次乘或除法。