[NOI 2012]乱数生成器[CodeVS 1281]Xn数列

テーマ説明Description
6個の数をあげますm,a,c,x 0,n,g
Xn+1=(aXn+c)mod m、Xnを求めます
m, a, c, x0, n, g<=10^18
入力記述Input Description
1行6個数m,a,c,x 0,n,g
出力記述Output Description
出力数Xn mod g
サンプル入力Sample Input
11 8 7 1 5 3
サンプル出力Sample Output
2
問題解

[xnc]=[xn−1c]⋅[a101]

直接行列乗算にかかわらずQQQQ

が爆発する

だから高速べき乗を真似て高速加算(a*b=a+a+a+.....+a)

を書く

もっと速くしたいなら、その2 X 2の行列の2列目は変わらないことに気づきます.

var
 m,a,c,x0,n,s,ans:int64;
 d,e,f,g:qword;
 t,y:array[1..2,1..2]of qword;
 i,j,k:longint;
function mmod(a,b:int64):qword;
var len:int64;
begin
 len:=0;
 while b<>0 do
  begin
   if (b and 1)=1
   then len:=(len+a)mod m;
   a:=(a*2)mod m;
   b:=b div 2;
  end;
 exit(len);
end;

begin
 readln(m,a,c,x0,n,s);
 t[1,1]:=1; t[1,2]:=0; t[2,1]:=0; t[2,2]:=1;
 y[1,1]:=a; y[1,2]:=0; y[2,1]:=1; y[2,2]:=1;
 while n<>0 do
  begin
   if (n and 1)=1
   then begin {t=t*y}
    d:=(mmod(t[1,1],y[1,1])+mmod(t[1,2],y[2,1]))mod m;
    e:=(mmod(t[1,1],y[1,2])+mmod(t[1,2],y[2,2]))mod m;
    f:=(mmod(t[2,1],y[1,1])+mmod(t[2,2],y[2,1]))mod m;
    g:=(mmod(t[2,1],y[1,2])+mmod(t[2,2],y[2,2]))mod m;
    t[1,1]:=d; t[1,2]:=e; t[2,1]:=f; t[2,2]:=g;
   end;
   {y=y*y}
   d:=(mmod(y[1,1],y[1,1])+mmod(y[1,2],y[2,1]))mod m;
   e:=(mmod(y[1,1],y[1,2])+mmod(y[1,2],y[2,2]))mod m;
   f:=(mmod(y[2,1],y[1,1])+mmod(y[2,2],y[2,1]))mod m;
   g:=(mmod(y[2,1],y[1,2])+mmod(y[2,2],y[2,2]))mod m;
   y[1,1]:=d; y[1,2]:=e; y[2,1]:=f; y[2,2]:=g;
   n:=n div 2;
  end;
 ans:=(((mmod(x0,t[1,1])+mmod(c,t[2,1])+m)mod m)+s)mod s;
 writeln(ans);
end.