快速幂||快速乘

求(a^b)%p或(a*b)%p

例如：因为7 = 4 + 2 + 1，那么 5^7 = 5^(4 + 2 + 1) = 5^4 * 5^2 * 5^1

​ 　　　幂： 5^7=5×56=5×(5²⁾3…

​ 　　　乘： 5×7=5+5×6=5+(5×2)×3…

#include<stdio.h>
#define ll long long
ll quick_pow(ll a,ll b,ll p){
    if(!b)
        return 1%p;
    ll ans=1%p;                      //ans=0
    while(b){						 
        if(b%2==1)
            b--,ans=(ans*a)%p;		 //ans=(ans+a)%p
        b/=2;
        a=(a*a)%p;					 //a=(a*2)%p
    }
    return ans;
}
int main()
{
    ll a,b,p;
    ll ans=1%p;
    scanf("%lld%lld%lld",&a,&b,&p);
    ans=quick_pow(a,b,p);
    printf("%lld\n",ans%p);
    return 0;
}

快速幂和快速乘的综合运用

数论—求A^B所有因数和

例题：POJ 1845

题意：求A^B的所有约数（即因子）之和，并对其取模9901再输出

题解：此处用的等比数列求和公式和用到逆元的知识：（ a/b ） mod c = （ a mod (b×c) ） / b
二分亦可解之
int 2147483648～2147483647 大约是2*10^9

#include<stdio.h>
#define ll long long
const int mod = 9901;
ll Mod;
ll A, B;
//快速乘
ll quick_mul(ll x, ll y) 
{
	ll ans = 0;
	while (y) {
		if (y & 1) ans = (ans + x) % Mod;
		y >>= 1;
		x = (x + x) % Mod;
	}
	return ans;
}
//快速幂
ll quick_pow(ll P, ll n) 
{
	ll ans = 1;
	while (n) {
		if (n & 1) ans = quick_mul(ans, P);//两数直接相乘溢出 
		n >>= 1;
		P = quick_mul(P, P);//两数直接相乘溢出
	}
	return ans;
}
int main() 
{
	while (~scanf("%lld%lld",&A, &B) ) {
		if (A == 0) {
			printf("0\n");
			continue;
		}
		int n;
		int ans = 1;
        //如果改成i<=A,则i最后是一个很大的素数
		for (int i = 2; i*i <= A; i++) { 
			if (A%i == 0) {
				n = 0;
				while (A%i == 0) {
					n++;
					A /= i;
				}
				Mod = mod * (i - 1);
                //等比数列求和
				ans = (ans*(quick_pow(i, B*n + 1) - 1) / (i - 1)) % mod;
                //B*n+1超出了int的范围 
			}
		}
		if (A > 1) {
			Mod = mod * (A - 1);
			ans = (ans*(quick_pow(A, B + 1) - 1) / (A - 1)) % mod;
		}
		printf("%d\n", ans);
	}
	return 0;
}

矩阵快速幂

矩阵的乘法:

1：c[i] [j]为A的第i行与B的第j列对应乘积的和，其前提为A的列数与B的行数相同

2：矩阵乘法是不满***换律的

我们一般采用**O(n^3)**的算法，当然也可以简化，简化算法不做详解

代码为

void mul(int a[N][N],int b[N][N],int n)
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
                c[i][j]+=a[i][k]*b[k][j];
}

矩阵快速幂

所谓矩阵快速幂即求A^n,其方法很简单，就是把快速幂中的乘法改成矩阵的乘法，可做乘法的重载

详细代码为

//int ans[][],a[][],N为矩阵大小
void mul(int a[N][N],int b[N][N],int n){...}
void quick_pow(int a[N][N],n)
{
    //单位矩阵对角线全是1，其余全是0
    for(int i=0;i<N;i++)
        ans[i][i]=1//ans矩阵相当于快速幂中初始化的1，这个矩阵叫做单位矩阵，即E*A=A，和1*a=a一样
    while(n){
        if(n&1){
            mul(ans,a,N);//res=res*a;
            n--;
        }
        n>>=1;
        mul(a,a,N);
    }
}

以上的是矩阵快速幂的思想以及实现方法，在实战中我们一般这样写：

完整实用的板子，以 hdu 1575为例

题意：A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。

输入：数据的第一行是一个T，表示有T组数据。
　　　每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数 据的范围是[0,9]，表示方阵A的内容。

输出：对应每组数据，输出Tr(A^k)%9973。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod = 9973;
int n, k;
struct nood {
	int arr[12][12];
};
nood init, unit;
nood Mul(nood a, nood b) {
	nood c;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			c.arr[i][j] = 0;
			for (int k = 0; k < n; k++)
				c.arr[i][j] +=  a.arr[i][k] % mod  * b.arr[k][j] % mod;
			c.arr[i][j] %= mod;
		}
	return c;
}
nood quick_Pow(nood a, nood b, int x) {
	while (x) {
		if (x & 1) {
			b = Mul(b, a);
			x--;
		}
		x >>= 1;
		a = Mul(a, a);
	}
	return b;
}
int main() 
{
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &k);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				scanf("%d", &init.arr[i][j]);
				unit.arr[i][j] = init.arr[i][j];
			}
		nood res = quick_Pow(init, unit, k - 1);
		int ans = 0;
		for (int i = 0; i < n; i++)
			ans += res.arr[i][i] % mod;
		printf("%d\n", ans%mod);
	}
	return 0;
}