快速幂的写法完全是我自己完成的哦,你们不要跟我强功,呵呵,
其实是自己找不到,呵呵;
没事自己写的感觉还不错呢.
快速幂取模就是用到了线性取模,呵呵.很简单的,.
现在贴出我的代码:
/*
*输入正整数a,n和m,输出a^n % m 的值,a,n,m <= 10^9;
*这是一个幂取模的题目
*下面的就是一个比较朴素的算法了,时间复杂度是O(n);
*/
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
/*
*运用二分,也就是分治法,快速求幂;
*/
using namespace std;
long long x = 1;
long long quick_pow(long long a, long long n, int m)
{
if (n == 1)
{
return a % m;
}
long long temp = quick_pow(a, n >> 1, m);
// cout << "temp = " << temp << endl;
if (n % 2 == 0)
{
// cout << "1" << endl;
x = (temp % m) * (temp % m);
}
else
{
// cout << "2" << endl;
x = temp %m * temp % m* a % m;
}
return x;
}
int main()
{
long long a, n, m;
scanf("%lld %lld %lld", &a, &n, &m);
long long ans = quick_pow (a, n, m);
printf("pow(a, n, m) == %lld\n", ans);
system("pause");
return 0;
}