菜鳥の高速べき乗理解

以前は高速べき乗について、どのように使うかしか知らなかったが、どの原理も分からなかった.コンピュータの構成原理とコンピュータネットワークを学んだ後、バイナリに敏感になった.8255のように、直接求めると255回の乗算を実行しなければならない.指数が大きいと、遅くなる.
255をバイナリで表すと8つの11111 1111ですが、実際には255=28*1+27*1+26*1+25*1+24*1+23*1+22*1+21*1+20*1=128+64+32+16+8+4+2+1+1+0指数をバイナリで表します.8(11111111)=8128*1*864*1*832*1*816*1*88*1*84*1*82*1*81*1*80*1で、右から左へカウントします.指数はそれぞれ128、64、32、16、8、4、2、1である.現在の指数は前の指数の2倍であるため、現在乗じなければならない数=前の乗数*前の乗数であり、現在の乗数がansに乗じられているかどうかは、現在位置するバイナリ数が1であるかどうかによって大きく減少する.もし数が大きいならば、テーマは型を取ることを要求して、毎回型を取ります.

#include 
using namespace std;
int qpow(int a, int b, int mod){
	int ans = 1, tmp = a;
	while(b){
		if(b & 1){
			ans = ans * tmp % mod;
		}
		tmp = tmp * tmp;
		b = b >> 1;
	}
	return ans % mod;
}
int main()
{
	int a, b;
	scanf("%d %d", &a, &b);	
	printf("%d", qpow(a, b, 100));
	return 0;
}

高速べき乗を理解するには,線形代数における行列の乗算を理解するだけで,行列高速べき乗は必ず理解できる.

#include 
#include 
using namespace std;
const int N = 1e2;
const int mod = 1e5;
struct abc{
	int t[N][N];
}a, ans;

void init(){
	for(int i = 1; i <= N; ++i){
		ans.t[i][i] = 1;
	}
}

struct abc x(struct abc a, struct abc b, int n){
	struct abc c;
	memset(c.t, 0, sizeof(c.t));
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			for(int k = 1; k <= n; ++k){
				c.t[i][j] = (c.t[i][j] +  (a.t[i][k] * b.t[k][j]) % mod) % mod;
			}
		}
	}
	return c;
}
int main()
{
	int b, n;
	scanf("%d %d", &b, &n);
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			scanf("%d", &a.t[i][j]);
		}
	}
	init();
	while(b){
		if(b & 1){
			ans = x(ans, a, n);
		}
		a = x(a, a, n);
		b = b >> 1;
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			printf("%d ", ans.t[i][j]);
		}
		printf("
");
	}
	return 0;
}