1:斐波那契数列第n项
在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)。
给定整数n，求Fibn mod10000。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含一个整数n。
当输入用例n=-1时，表示输入终止，且该用例无需处理。
输出格式
每个测试用例输出一个整数表示结果。
每个结果占一行。
数据范围
0≤n≤2∗109
输入样例：
0
9
999999999
1000000000
-1
输出样例：
0
34
626
6875
思路：矩阵快速幂 ， 每次取模 。
#include <stdio.h>
#include <string.h>
long long n,mod=10000;
void Matrix1(long long a[2],long long b[2][2])
{
long long c[2]={0};
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
c[j]=(c[j]+a[k]*b[k][j]%mod)%mod;
}
}
memcpy(a,c,sizeof(c));
}
void Matrix2(long long b[2][2])
{
long long c[2][2]={0};
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]+b[i][k]*b[k][j]%mod)%mod;
}
}
}
memcpy(b,c,sizeof(c));
}
int main()
{
while(~scanf("%lld",&n))
{
if(n==-1) break;
else
{
long long a[2]={0,1};
long long b[2][2]={0,1,1,1};
while(n)
{
if(n&1) Matrix1(a,b);
Matrix2(b);
n>>=1;
}
printf("%lld
",a[0]);
}
}
return 0;
}
2:斐波那契数列 10’
描述
已知斐波那契数列 1，1，2，3，5，8，13，21每一项是前两项的和。
请告诉laofu，第202003281331项的最后一位是多少。（大家写到这题，是不是这个时间呢，嘿嘿~）
例如：第八项的最后一位是1
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个数字，填写多余的内容将无法得分。
思路：最后一位只和最后一位有关，所以每次模10取最后一位。
#include <stdio.h>
#include <string.h>
long long n,mod=10,a[2]={0,1},b[2][2]={0,1,1,1};
void Matrix1(long long a[2],long long b[2][2])
{
long long c[2]={0};
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
c[j]=(c[j]+a[k]*b[k][j]%mod)%mod;
}
}
memcpy(a,c,sizeof(c));
}
void Matrix2(long long b[2][2])
{
long long c[2][2]={0};
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]+b[i][k]*b[k][j]%mod)%mod;
}
}
}
memcpy(b,c,sizeof(c));
}
int main()
{
scanf("%lld",&n);
while(n)
{
if(n&1) Matrix1(a,b);
Matrix2(b);
n>>=1;
}
printf("%lld
",a[0]);
return 0;
}