快速幂和矩阵乘法
由于[1 1][1 0] 的n次方 等于 [fn+1 fn ][fn fn-1]
所以可以用快速幂求n次方
不过乘法是矩阵乘法的乘
顺带一提inline是内联函数,以直接插入语句而非调用的方式运作
n–则是因为一开始f就是{1,1}{1,0}的1次方,所以n要-1
#include<bits/stdc++.h>
using namespace std;
const int m = 10000;
int a[2][2],f[2][2];
inline void mul(int a[2][2],int f[2][2])
{
int c[2][2]; memset(c,0,sizeof c);
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
c[i][j]=(c[i][j]+(long long)a[i][k]*f[k][j])%m;//记得一定要开long long
memcpy(f,c,sizeof c);
}
void qmi(int n)
{
n--;
a[0][0] = a[0][1] = a[1][0] = 1; a[1][1] = 0;
memcpy(f,a,sizeof f);
while (n)
{
if (n & 1)mul(a, f);
n = n >> 1;
mul(a,a);
}
cout << f[0][1] << endl;
}
int main()
{
int n;
while (cin >> n)
{
if (n == -1)break;
if(n==0)
cout<<0<<endl;
else
qmi(n);
}
}