高速べき乗アルゴリズムとマトリクス高速べき乗

Description
3つの数A,B,Kを与え,AのB次方をKの残数で割った.
Input
入力は1行のみで、3つの正の整数A(1<=A<=20000000)、B(1<=B<=20000000)、K(1<=K<=10000)である.
Output
整数(A^B)%Kの値です.
Sample Input
11 100 7
Sample Output
4

#include<iostream>
using namespace std;
int main()
{
	long long a,b;
	int k,i,j,s=1;
	cin>>a;
	cin>>b;
	cin>>k;
	a=a%k;
	while(b)
	{
		if(b%2==1)
			s=(s*a)%k;
		b=b/2;
		a=(a*a)%k; 
	}
	cout<<s<<endl;
	return 0;
}

以下はa^b高速べき乗アルゴリズムテンプレート

	int s=1,a,b;
        cin>>a>>b;
	while(b)
	{
		if(b%2==1)
		<span style="white-space:pre">	</span>s=s*a;
		b=b/2;
		a=a*a; 
	}
	cout<<s<<endl;

マトリックス高速べき乗アルゴリズムを用いてフィボナッチ数列を求める
Description
In the Fibonacci integer sequence, 
F
0 = 0, 
F
1 = 1, and 
Fn = 
Fn
 − 1 + 
Fn
 − 2 for 
n ≥ 2. F
Input
a single line containing n (where 0 ≤ 
n ≤ 100,000,000,000)
Output
print 
Fn mod 1000000007 in a single line.
Sample Input

99999999999

Sample Output

669753982

Hint
An alternative formula for the Fibonacci sequence is
As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by
Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:
ACコード//マトリックス高速べき乗型テンプレート

#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
long long a[3][3]={{0,0,0},{0,1,1},{0,1,0}};
long long t[3][3]={{0,0,0},{0,0,0},{0,0,0}};//   temp，    
long long s[3][3]={{0,0,0},{0,1,0},{0,0,1}};//       
int main()
{
	int k,i,j;
	long long n,b;
	cin>>n;
	b=n;
	while(b)
	{
		if(b%2==1)
		{
		    memset(t,0,sizeof(t));
			for(i=1;i<=2;i++)
				for(j=1;j<=2;j++)
				 	for(k=1;k<=2;k++)
				 		t[i][j]=(t[i][j]+(s[i][k]*a[k][j])%1000000007)%1000000007;//t=s*a
			for(i=1;i<=2;i++)
				for(j=1;j<=2;j++)
				s[i][j]=t[i][j];//s=t;
		}
		b=b/2;
		memset(t,0,sizeof(t));
		for(i=1;i<=2;i++)
			for(j=1;j<=2;j++)
				for(k=1;k<=2;k++)
					t[i][j]=(t[i][j]+(a[i][k]*a[k][j])%1000000007)%1000000007;//t=a*a;
		for(i=1;i<=2;i++)
			for(j=1;j<=2;j++)
			a[i][j]=t[i][j];//a=t;		
	}
	cout<<s[1][2]<<endl;
	return 0;
}