题解 P4000 【斐波那契数列】

· · 题解

来篇Pascal题解。

对于这道题，Pascal的读入效率不用说，但是动态字符串真是太丢人了……

毕竟是用链表实现的，访问的时候不慢才怪

TLE后3个点。

果断使用字符数组。

没有strlen这样的东西，就一个一个遍历下来，不是数字就退出。

AC。

具体实现不讲了，就是求循环节然后矩阵快速幂。

求循环节什么的看这里：Fib数模n的循环节

如果看懂了写代码也不难了。（也就是模拟嘛）

丢代码：

type
  matrix=array[1..2,1..2]of int64;//因为p太大要开int64
var
  a1,t1:array[1..60000]of longint;
  i,p,num:longint;
  x,s:int64;
  a,t:matrix;
  n:array[0..30000001]of char; //坑点：一定要多出一位（我也不知道为什么，但是WA了好几次）
function gcd(x,y:int64):int64; //不解释
var
  r:int64;
begin
  while y>0 do
  begin
    r:=x mod y;
    x:=y;
    y:=r;
  end;
  exit(x);
end;
function lcm(x,y:int64):int64; //不解释
begin
  exit(x div gcd(x,y)*y);
end;
function solve(x:longint):int64;//求解循环节
var
  i:longint;
begin
  for i:=2 to trunc(sqrt(x)) do
    if x mod i=0 then
    begin
      inc(num);
      a1[num]:=1;
      t1[num]:=i;
      x:=x div i;
      while x mod i=0 do
      begin
        x:=x div i;
        a1[num]:=a1[num]*i;
      end;
    end;
  if x>1 then
  begin
    inc(num);
    a1[num]:=1;
    t1[num]:=x;
  end;
  solve:=1;
  for i:=1 to num do
    case t1[i] of
    2:solve:=lcm(solve,int64(a1[i])*3);
    3:solve:=lcm(solve,int64(a1[i])*5);
    5:solve:=lcm(solve,int64(a1[i])*20);
    else if (t1[i] mod 5=1) or (t1[i] mod 5=4) then
    solve:=lcm(solve,int64(a1[i])*(t1[i]-1))
    else
    solve:=lcm(solve,int64(a1[i])*((t1[i]+1) shl 1));
  end;
end;
operator *(a,b:matrix)c:matrix;//矩阵乘法的实现
begin
  c[1,1]:=(a[1,1]*b[1,1] mod p+a[1,2]*b[2,1] mod p) mod p;
  c[1,2]:=(a[1,1]*b[1,2] mod p+a[1,2]*b[2,2] mod p) mod p;
  c[2,1]:=(a[2,1]*b[1,1] mod p+a[2,2]*b[2,1] mod p) mod p;
  c[2,2]:=(a[2,1]*b[1,2] mod p+a[2,2]*b[2,2] mod p) mod p;
end;
function power(x:matrix;y:int64):matrix;//矩阵快速幂
begin
  power[1,1]:=1;
  power[2,2]:=1;
  while y>0 do
  begin
    if odd(y) then
      power:=power*x;
    x:=x*x;
    y:=y shr 1;
  end;
end;
begin                          //简单的主程序
  readln(n);
  read(p);
  if p=1 then                  //特判啦啦啦
  begin
    writeln(0);
    halt;
  end;
  x:=solve(p);
  s:=0;
  for i:=0 to 30000001 do      //Pascal用char读入会超时……只好这样读入后取模了
    if (n[i]>='0') and (n[i]<='9') then
      s:=(s*10+ord(n[i])-48) mod x
    else
      break;
  if s=0 then                  //斐波那契数列特判
  begin
    writeln(0);
    halt;
  end;
  if s<=2 then
  begin
    writeln(1);
    halt;
  end;
  a[1,1]:=1;                  //矩阵快速幂啦啦啦
  a[1,2]:=1;
  a[2,1]:=1;
  a[2,2]:=0;
  t:=power(a,s-2);
  writeln((t[1,1]+t[1,2]) mod p);
end.