INFOMAN брой 20

{ Входни данни :
2 6 4

XVII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА

Първи ден - Задача 2. Степен

Дадени са целите числа N, M и Y (0 < N < 999, 1 < M < 999, 
0 < Y < 999). Напишете програма POWER.EXE, която намира 
всичките цели числа X (X = 0,  1, ..., M -1), за всяко от 
които е изпълнено, че при деление с M на N-тата степен на 
X се получава остатък Y, т.е. X N mod M = Y.

Входните данни се четат от текстов файл POWER.INP, който 
съдържа целите числа N, M и Y, написани на един ред и 
разделени с по една шпация.

Резултатът от програмата трябва да бъде записан като редица 
от едно или повече различни цели числа, разделени с по една 
шпация, и подредени в нарастващ ред в изходния текстов файл 
POWER.OUT. Ако такива числа не съществуват, програмата 
трябва да запише числото -1.

РЕШЕНИЕ:

Основното за задачата е, че трябва да извършваме умноженията под модул,
което елиминира нуждата от големи числа. Тоест за да пресметнем X^N mod M,
можем да използваме следния код :

result := 1;
for i := 1 to N do
  result := (result * X) mod M;

Сложноста е O(N), което може да бъде подобрено до O(logN).
Ето и кода реализиращ O(logN) :

result := 1;
NT := N;
XT := X;
while NT <> 0 do
begin
  if odd(NT) then
  begin
    dec(NT);
    result := (result * XT) mod M;
  end else
  begin
    NT := NT div 2;
    XT := (XT * XT) mod M;
  end;
end;

Вижда се, че през цялото време на изпълнение на горния код се запазва
инвариантата (XT^NT * result) mod M = X^N mod M. След изход от while цикъла
в result е резултата, защото NT = 0. Сложноста е O(logN), защото след всеки
две итераций, NT задължително намалява поне 2 пъти.

Jivko Ganev
}

const
  infile = 'power.pas';
  outfile = 'power.out';

var
  n, m, y : longint;
  flag : boolean;
  fout : text;

procedure indata;
var fin : text;
begin
  assign(fin, infile);
  reset(fin);
  readln(fin); {Входа се чете от сорса}
  read(fin, n, m, y);
  close(fin);
end;

function bigmod(x, n : longint) : longint;
var res : longint;
begin
  res := 1;
  while n <> 0 do
  begin
    if NOT odd(n) then
    begin
      n := n div 2;
      x := (x * x) mod m;
    end;
    if odd(n) then
    begin
      res := (res * x) mod m;
      dec(n);
    end;
  end;
  bigmod := res;
end;

procedure solve;
var x : longint;
begin
  for x := 0 to m-1 do
    if bigmod(x, n) = y then
    begin
      write(fout, x, ' ');
      flag := true;
    end;
end;

begin
  assign(fout, outfile);
  rewrite(fout);
  indata;
  solve;
  if NOT flag then writeln(fout, -1);
  close(fout);
end.