Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- program polinom;
- {$mode objfpc}{$H+}
- uses crt;
- var
- N, i, j: integer;
- k, FreeFac, PrevFact, P, Cons: UInt64;
- C, StdPol: array of UInt64;
- function add(a, b: UInt64): UInt64;
- begin
- if a < (P - b) then
- Result := a + b
- else
- Result := b - (P - a);
- Result := Result mod P;
- end;
- function sub(a, b: UInt64): UInt64;
- begin
- Result := add(a, P-b);
- end;
- function mult(a, b: UInt64): UInt64;
- var
- k: UInt64;
- begin
- Result := 0;
- k := a;
- while b <> 0 do
- begin
- if (b mod 2) = 1 then
- begin
- Result := add(Result, k);
- b -= 1;
- end
- else
- begin
- b := b div 2;
- k := add(k, k);
- end;
- end;
- end;
- begin
- assign(input, 'input.txt'); reset(input);
- assign(output, 'output.txt'); rewrite(output);
- P := 100;
- read(P, N);
- setlength(C, N);
- read(Cons);
- if P <> 0 then
- Cons := Cons mod P;
- for i:=0 to N-1 do
- begin
- read(C[i]);
- C[i] := C[i] mod P;
- end;
- if length(C) > 1 then
- begin
- Setlength(StdPol, 3);
- StdPol[0] := 1;
- StdPol[1] := (P-C[0]) mod P;
- end;
- for i:=1 to high(C) do
- begin
- FreeFac := StdPol[high(StdPol)-1];
- PrevFact := StdPol[0];
- for j:=1 to high(StdPol)-1 do
- begin
- k := StdPol[j];
- StdPol[j] := sub(StdPol[j], mult(C[i], PrevFact));
- PrevFact := k;
- end;
- StdPol[high(StdPol)] := mult((P-C[i])mod P, FreeFac);
- Setlength(StdPol, length(StdPol)+1);
- end;
- if length(StdPol) > 0 then
- Setlength(StdPol, length(StdPol)-1)
- else
- writeln(Cons);
- for i:=high(StdPol) downto 0 do
- writeln(mult(Cons, StdPol[i]));
- close(input);
- close(output);
- end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement