Advertisement
Guest User

Untitled

a guest
Jan 18th, 2018
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 1.66 KB | None | 0 0
  1. program polinom;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. uses crt;
  6.  
  7. var
  8.     N, i, j: integer;
  9.   k, FreeFac, PrevFact, P, Cons: UInt64;
  10.   C, StdPol: array of UInt64;
  11.  
  12.  
  13. function add(a, b: UInt64): UInt64;
  14. begin
  15.     if a < (P - b) then
  16.     Result := a + b
  17.   else
  18.     Result := b - (P - a);
  19.  
  20.   Result := Result mod P;
  21. end;
  22.  
  23. function sub(a, b: UInt64): UInt64;
  24. begin
  25.     Result := add(a, P-b);
  26. end;
  27.  
  28. function mult(a, b: UInt64): UInt64;
  29. var
  30.   k: UInt64;
  31. begin
  32.   Result := 0;
  33.   k := a;
  34.  
  35.   while b <> 0 do
  36.     begin
  37.     if (b mod 2) = 1 then
  38.     begin
  39.       Result := add(Result, k);
  40.       b -= 1;
  41.     end
  42.     else
  43.     begin
  44.       b := b div 2;
  45.       k := add(k, k);
  46.     end;
  47.   end;
  48. end;
  49.  
  50. begin
  51.   assign(input, 'input.txt'); reset(input);
  52.   assign(output, 'output.txt'); rewrite(output);
  53.   P := 100;
  54.   read(P, N);
  55.   setlength(C, N);
  56.   read(Cons);
  57.   if P <> 0 then
  58.         Cons := Cons mod P;
  59.  
  60.   for i:=0 to N-1 do
  61.   begin
  62.     read(C[i]);
  63.     C[i] := C[i] mod P;
  64.   end;
  65.  
  66.   if length(C) > 1 then
  67.   begin
  68.     Setlength(StdPol, 3);
  69.     StdPol[0] := 1;
  70.     StdPol[1] := (P-C[0]) mod P;
  71.   end;
  72.   for i:=1 to high(C) do
  73.   begin
  74.     FreeFac := StdPol[high(StdPol)-1];
  75.     PrevFact := StdPol[0];
  76.     for j:=1 to high(StdPol)-1 do
  77.     begin
  78.       k := StdPol[j];
  79.       StdPol[j] := sub(StdPol[j], mult(C[i], PrevFact));
  80.       PrevFact := k;
  81.     end;
  82.     StdPol[high(StdPol)] := mult((P-C[i])mod P, FreeFac);
  83.     Setlength(StdPol, length(StdPol)+1);
  84.   end;
  85.   if length(StdPol) > 0 then
  86.     Setlength(StdPol, length(StdPol)-1)
  87.   else
  88.     writeln(Cons);
  89.  
  90.  
  91.   for i:=high(StdPol) downto 0 do
  92.     writeln(mult(Cons, StdPol[i]));
  93.  
  94.  
  95.   close(input);
  96.   close(output);
  97. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement