斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........
题目描述
广义的斐波那契数列是指形如an=p*an-1+q*an-2的数列。今给定数列的两系数p和q，以及数列的最前两项a1和a2，另给出两个整数n和m，试求数列的第n项an除以m的余数。
输入输出格式
输入格式：
输入包含一行6个整数。依次是p,q,a1,a2,n,m，其中在p,q,a1,a2整数范围内，n和m在长整数范围内。
输出格式：
输出包含一行一个整数，即an除以m的余数。
此题为斐波拉契数列的一个变形，即递推公式为f[i]=f[i-1]*a+f[i-2]*b；将矩阵变形即可。
type
rec =record
v :array[..,..] of longint;
end; var
n,m,i,j,p,q,a1,a2 :longint;
jz,ans :rec; function mul(a,b:rec):rec;
var
c :rec;
begin
c.v[,]:=(a.v[,]*b.v[,]+a.v[,]*b.v[,]+m) mod m;
c.v[,]:=(a.v[,]*b.v[,]+a.v[,]*b.v[,]+m) mod m;
c.v[,]:=(a.v[,]*b.v[,]+a.v[,]*b.v[,]+m) mod m;
c.v[,]:=(a.v[,]*b.v[,]+a.v[,]*b.v[,]+m) mod m;
exit(c);
end; function pow(a:rec; k:longint):rec;
begin
if k= then exit(a);
a:=pow(a,k>>);
if k mod = then exit(mul(a,a)) else exit(mul(mul(a,a),jz));
end; begin
read(p,q,a1,a2,n,m);
jz.v[,]:=;
jz.v[,]:=q;
jz.v[,]:=;
jz.v[,]:=p;
ans:=pow(jz,n-);
writeln(((ans.v[,]*a1+ans.v[,]*a2) mod m));
end.
Problem 2：Fibonacci
【问题描述】
斐波拉契有如下性质：F[1]=1,f[2]=1;F[n]=F[n-1]+F[n-2]是fibonacci的递推吧，求两项的最大公约数。
【输入】
第一行输入一个整数gay；gay<=10
接下来的gay行，每行两个整数gay_a,gay_b；
【输出】
共gay行，每行一个整数，表示F[gay_a]和F[gay_b]最大公约数。（在MOD 19491001意义下）。
input：
5
30 15
14 28
12 24
17 17
30 6
output：
610
377
144
1597
8
我们先来看Fibonacci数列的几个引论
引理1：
Gcd(F[n+1],F[n])=1;
证明：
根据辗转相减法则
Gcd(F[n+1],F[n])=Gcd(F[n+1]-F[n],F[n])=Gcd(F[n],F[n-1])=Gcd(F[2],F[1])=1；
引理2：
F[m+n]=F[m-1]F[n]+F[m]F[n+1]
证明：
F[n+m]=F[n+m-1]+F[n+m-2]=2*F[n+m-2]+F[n+m-3]=……
F[n+m]=a[x]*F[n+m-x]+b[x]*F[n+m-x-1]=a[x]*(F[n+m-x-1]+F[n+m-x-2])+b[x]*(F[n+m-x-1)=(a[x]+b[x])*F[n+m+x-1]+a[x]*F[n+m+x-2];
当x=1时有 a[1]=F[2]; b[1]=F[1];
当x=2时有 a[2]=F[2]+F[1]=F[3]; b[2]=a[1]=F[2];
当x=k+1时有 a[k+1]=a[k]+b[k]=F[k+1]+F[k]=F[k+2] b[k+1]=a[k]=F[k+1];
所以当x=n时 F[n+m]=a[n]F[m]+b[n]F[m-1]=F[n+1]F[m]+F[n]F[m-1];
引理3：
Gcd(F[n+m],F[n])=Gcd(F[n],F[m])
证明：
Gcd(F[n+m],F[n])=Gcd(F[n+1]F[m]+F[n]F[m-1],F[n])=Gcd(F[n+1]F[m],F[n])=Gcd(F[n+1],F[n])*Gcd(F[m],F[n])=Gcd(F[m],F[n]);
由以上三个引理有：Gcd(F[n],F[m])=F[Gcd(n,m)];
如果不会证明也不知道结论怎么办？打表找规律即可AC。（像我一样）
const mo=;
type
rec =record
v :array[..,..] of int64;
end; var
m,a,b :rec;
n,i,j :longint;
gc,x,y :int64; procedure csh;
begin
m.v[,]:=;
m.v[,]:=;
m.v[,]:=;
m.v[,]:=;
end; function mul(a,b:rec):rec;
var
c :rec;
begin
c.v[,]:=(a.v[,]*b.v[,]+a.v[,]*b.v[,]+mo) mod mo;
c.v[,]:=(a.v[,]*b.v[,]+a.v[,]*b.v[,]+mo) mod mo;
c.v[,]:=(a.v[,]*b.v[,]+a.v[,]*b.v[,]+mo) mod mo;
c.v[,]:=(a.v[,]*b.v[,]+a.v[,]*b.v[,]+mo) mod mo;
exit(c);
end; function pow(a:rec; k:int64):rec;
begin
if k= then exit(a);
a:=pow(a,k>>);
if k mod = then exit(mul(a,a)) else exit(mul(mul(a,a),m));
end; function gcd(a,b:int64):int64;
begin
if (b=) then exit(a);
exit(gcd(b,a mod b));
end; begin
read(n);
for i:= to n do
begin
csh;
read(x,y);
gc:=gcd(x,y);
a:=pow(m,gc);
writeln(a.v[,]);
end;
end.
Problem 3： 黄金分割比
【问题描述】
把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。其比值是一个无理数，用分数表示为(√5-1)/2，取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这个分割点就叫做黄金分割点（golden section ratio通常用φ表示）这是一个十分有趣的数字，我们以0.618来近似表示，通过简单的计算就可以发现：(1-0.618)/0.618=0.6一条线段上有两个黄金分割点。
现在LS要对这个数进行研究，首先他就要想办法用分数逼近黄金数。当然，他需要你给他的是离黄金数的差最小的分数。
【输入】
输入文件只有一行，这一行有一个数N(1≤N≤10^19)，表示逼近的分数分母≤N。
【输出】
输出文件只有一行，这一行有一个分数，格式为“x/y”，为你所输出的分数。
【输入输出样例】
Gold.in
10
Gold.out
5/8
给出一个结论即可：而且当n趋向于无穷大时，斐波拉契数列前一项与后一项的比值越来越逼近黄金分割0.618，自己证明。
注意，此题n较大，爆掉int64，需要特判一下。（或者你可以用高精）
var
f :Array[..] of int64;
i,l :longint;
s :int64;
st :string;
std :string;
begin
f[]:=;
f[]:=;
for i:= to do f[i]:=f[i-]+f[i-];
std:='';
readln(st);
l:=length(st);
if (l<) or ((l=) and (st<=std)) then
begin
val(st,s);
if (s=) or (s=) then writeln('1/1') else
begin
for i:= to do if s<=f[i] then break;
if s=f[i] then writeln(f[i-],'/',f[i]) else writeln(f[i-],'/',f[i-]);
end;
end else
begin
writeln('4660046610375530309/7540113804746346429');
end;
end.