二分求幂（一种快速幂运算的方法）

求a的b次方，运用二分求幂的方法  ——通过将b转换成二进制进行分解

//普通二分求幂
long long pow(long long q, long long k) {  //q的k次方
    long long ans=1;
    while (k!=0) {
        if (k % 2 == 1) {
            ans *= q;
            ans %= M; //如果有大数保留要求
        }
        k /= 2;
        q *= q;
        q %= M;  //如果有大数保留要求
    }
    return ans;
}

//矩阵二分求幂
Matrix pow(Matrix tr,int k) {
	int i, j;
	Matrix ans;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			ans.m[i][j] = (i == j);
		}
	}
	while (k != 0) {
		if (k % 2 == 1) {
			ans=Mul(ans,tr);
		}
		k /= 2;
		tr=Mul(tr, tr);
	}
	return ans;
}

例一 九度1441 人见人爱A^b

题目描述：

求A^B的最后三位数表示的整数。说明：A^B的含义是“A的B次方”

输入：

输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。

输出：

对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。

样例输入：

2 3
12 6
6789 10000
0 0

样例输出：

8
984
1

#include<stdio.h>
int main() {
	int a, b;
	while (scanf("%d %d", &a, &b) != EOF) {
		int ans=1;
		if (a == 0 && b == 0) break;
		while (b != 0) {
			if (b % 2 == 1) {
				ans *= a;
				ans %= 1000;  //取后三位
			}
			b /= 2;
			a *= a;
			a %= 1000;  //取后三位
		}
		printf("%d\n", ans);
	}
	return 0;
}

例二 九度1442 

A sequence of numbers

题目描述：

Xinlv wrote some sequences on the paper a long time ago, they might be arithmetic or geometric sequences. The numbers are not very clear now, and only the first three numbers of each sequence are recognizable. Xinlv wants to know some numbers in these sequences, and he needs your help.

输入：

The first line contains an integer N, indicting that there are N sequences. Each of the following N lines contain four integers. The first three indicating the first three numbers of the sequence, and the last one is K, indicating that we want to know the K-th numbers of the sequence.

You can assume 0 < K <= 10^9, and the other three numbers are in the range [0, 2^63). All the numbers of the sequences are integers. And the sequences are non-decreasing.

输出：

Output one line for each test case, that is, the K-th number module (%) 200907.

样例输入：

2
1 2 3 5
1 2 4 5

样例输出：

5
16

    

#include<stdio.h>
#define M 200907
long long dengcha(long long a, long long d, long long k) {
	long long ans;
	ans = (a%M + (((k - 1)%M)*(d%M))%M)%M;
	return ans;
}

long long dengbi(long long a, long long q, long long k) {
	long long ans=1;
	k--;
	while (k!=0) {
		if (k % 2 == 1) {
			ans *= q;
			ans %= M;
		}
		k /= 2;
		q *= q;
		q %= M;
	}
	return ans*a;
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		while (n--) {
			long long a, b, c;
			int k;
			long long t;
			scanf("%lld %lld %lld %d", &a, &b, &c, &k);
			if (c - b == b - a) {
				t = c - b;
				printf("%lld\n",dengcha(a, t,k));
			}
			else {
				t = b / a;
				printf("%lld\n", dengbi(a, t,k));
			}
		}
	}
}

例三 九度1443

Tr A（矩阵快速幂）

题目描述：

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。

样例输入：

2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9

样例输出：

2

2686

#include<stdio.h>
#define M 9973
int n;
//定义矩阵结构体
struct Matrix {
	int m[11][11];
};
//定义矩阵相乘
Matrix Mul(Matrix a,Matrix b) {
	int i, j, k;
	Matrix c;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			c.m[i][j] = 0;
			for (k = 0; k < n; k++) {
				c.m[i][j] =(c.m[i][j]+ a.m[i][k] * b.m[k][j])%M;
			}
		}
	}
	return c;
}
//定义二分求幂
Matrix pow(Matrix tr,int k) {
	int i, j;
	Matrix ans;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			ans.m[i][j] = (i == j);
		}
	}
	while (k != 0) {
		if (k % 2 == 1) {
			ans=Mul(ans,tr);
		}
		k /= 2;
		tr=Mul(tr, tr);
	}
	return ans;
}
int main() {
	int T;
	while (scanf("%d", &T) != EOF) {
		while (T--) {
			int i, j;
			int k;
			int sum=0;  //对角线和
			Matrix tr; //原始矩阵tr
			Matrix c; //pow之后的结果矩阵
			scanf("%d %d", &n, &k);
			//输入矩阵tr
			for (i = 0; i < n; i++) {
				for (j = 0; j < n; j++) {
					scanf("%d", tr.m[i]+j);
				}
			}
			//计算矩阵幂
			c = pow(tr, k);
			//求主对角线和
			for (i = 0; i < n; i++) {
				sum=(sum+c.m[i][i]) % M;
			}
			printf("%d\n", sum);
		}
	}
}