c.s[i] = 0;
// 余数d大于除数b时，才可以进行减操作
while ((j=HPCompare(d,b)) >= 0)
{
Subtract(d, b, d);
c.s[i]++;
if (j == 0) break;
}
}
c.len = a.len;
while (c.len > 1 && c.s[c.len] == 0)
c.len--;
}
#define MAXSIDE 3
struct Matrix{int side; HP a[MAXSIDE][MAXSIDE];};
// 方阵的乘法
void MatrixMulti(const Matrix x, const Matrix y, Matrix& z)
{
if (x.side != y.side) return;
HP tmp;
z.side = x.side;
for (int i=0; i
z.a[i][j].len=1; z.a[i][j].s[1]=0;
for (int k=0; k
Multi(x.a[i][k], y.a[k][j], tmp);
Plus(z.a[i][j], tmp, z.a[i][j]);
}
}
}
// 方阵的幂次运算
void MatrixPower(const Matrix x, Matrix &y, int n)
{
y.side = x.side;
int i, j;
for (i=0; i
y.a[i][j].len = 1;
y.a[i][j].s[1] = 0;
}
for (i=0; i
y.a[i][i].len = 1;
y.a[i][i].s[1] = 1;
}
Matrix tmp = x;
// 只需要O(logn)的复杂度就能算出x的n次幂
while (n)
{
// 如果n的最低二进制位为1，则乘上对应的幂次tmp
if ((n&1) == 1)
MatrixMulti(y, tmp, y);
MatrixMulti(tmp, tmp, tmp);
// n移位
n >>= 1;
}
}
int main()
{
int n;
Matrix tmp;
tmp.side = 2;
tmp.a[0][0].len=tmp.a[0][1].len=tmp.a[1][0].len=tmp.a[1][1].len=1;
tmp.a[0][0].s[1] = 1; tmp.a[0][1].s[1] = 1;
tmp.a[1][0].s[1] = 1; tmp.a[1][1].s[1] = 0;
while (cin >> n)
{
Matrix x = tmp, y;
MatrixPower(x, y, n-1);
HP fn = y.a[0][0];
PrintHP(fn);
cout << endl;
}
}
作者：linyunzju