算法问题1：x^n mod 1003

x^n mod 1003

Description
给定整数x和n,求x的n次幂 mod 1003

Input
整数x和n。 1<=x,n<=1,000,000,0000

Output
x^n mod 1003

Sample Input
2 10
Sample Output
21
HINT
两种方法：
1、二进制方法
2、递归算法

递归算法

思路

假设我们要求2的10次方，那么我们可以先求2的5次方，然后再将两个2的5次方相乘；而对于2的5次方同样可以如此，不断二分，直到2的0次方；
因为任何值的0次方都是1，所以以此作为二分递归结束的标志；
此时，我们已经将幂分到0，需要向前递归，如果递归到的n为偶数，即上一层的x的n/2次方、这一层的x的n次方的n为偶数，那么我们只需将之前已经递归求出的这一层的x的n/2次方乘自己一次即可；如果递归到的n为奇数，除了乘自己一次还需要在乘一个x。
例如：已经求出x的0次方等于1，递归到上一层为x的1次方，x的0次方的结果存在一个变量ans中，则x的1次方=ansansx；再递归到上一层，假设为x的3次方（且此时ans存了x的1次方的结果），3为奇数，x的3次方=x的1次方x的1次方x=ansansx；再递归到上一层，假设为x的6次方，此时ans存了x的3次方的结果，则x的6次方=ans*ans；依此类推。
另外：别忘了每递归一次对1003取一次余

代码

#include 
#include 
#include 
#include 
#include 
#include using namespace std;static int MOD = 1003;long long power(long long x,long long n)
{long long ans;if(n==0)return 1;ans = power(x,n/2);if(n%2==1)return ans*ans*x%MOD;elsereturn ans*ans%MOD;
}int main()
{long long x,n,ans;cin >> x >> n;ans = power(x,n);cout << ans << endl;return 0;
}

二进制算法

思路

思路其实和递归法是一样的，只是实现的方式不一样而已；
同样是将幂不断二分直到分到0结束
在循环中，每次循环将x的值更新为xx，并将n二分；在n不断二分直到n==0循环结束，n每变成一次奇数就需要在结果ans中多乘一次x，n若是偶数则只需更新x的值为xx即可，如此，在n==0循环结束后，x*x的最终结果同ans的积刚好等于x的n次方的结果；
因为电脑中所有整数不断除以2之后的结果都会是1，1是奇数，所以最终结果都会乘到ans上，所以ans初值设为1，而1除以2又得0，刚好结束循环输出结果

代码

#include 
#include 
#include 
#include 
#include 
#include using namespace std;static int MOD = 1003;int main()
{long long x,n,ans=1;cin >> x >> n;x%=1003;while(n>0){if(n&1==1)ans=ans*x%MOD;x=x*x%MOD;n>>=1;}//我感觉并不算纯粹的二进制方法//将n>>=1和n&1换成n/2和n%2也是一样的效果cout << ans << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！