Блог пользователя bardakov_a_a

Автор bardakov_a_a, 12 лет назад, По-русски

Дамы и Господа! Нужна Ваша помощь. Решил заняться олимпиадным программированием и вот пока встречаю камни предкновения. Решал задачу с Timus 1110 Степень http://acm.timus.ru/problem.aspx?space=1&num=1110 1110. Степень Ограничение времени: 0.5 секунды Ограничение памяти: 16 МБ Даны целые числа N, M и Y. Напишите программу, которая найдёт все целые числа X в диапазоне [0, M – 1], такие что XN mod M = Y. Исходные данные Ввод содержит единственную строку с числами N, M и Y (0 < N < 999, 1 < M < 999, 0 < Y < 999), записанными через пробел. Результат Выведите все числа X через пробел в одной строке. Числа должны идти в порядке возрастания. Если искомых чисел нет, выведите −1.

Вот собственно код

program Project2;

{$APPTYPE CONSOLE}

var
  N,M,Y: Word;
  i: Word;
  found: Boolean;

function Power(i: Word; N: Word): Integer;
var res: Integer;
begin
  if odd(N) then  res:=i
  else res := 1;
  while N>1 do
  begin
    N:=N div 2;
    i:=i*i;
    if odd(N) then
      res:=res*i;
  end;
  Power:=res;
end;

function Left(x: Integer; y, n: Integer): Integer;
begin
  Left:=Power(x mod n, y) mod n;
end;

begin
  ReadLn(N, M, Y);
  found:=true;
  for i := 0 to M --- 1 do
    if Left(i, N, M) = Y then
    begin
      Write(i, ' ');
      found:=false;
    end;
  if found then Write(-1);
end.


Валиться на 6 тесте. Предполагаю не укладывается по времени, но я уже не знаю как ее еще улучшить. Помогите кто чем сможет

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Валится не по времени, а из-за неправильного ответа(если ваш тимусовский ник, конечно, Artem)

Проблема в том, что когда вы возносите число X в степень N, оно может быть достаточно большим(998^998). Стандартные типы данных не поддерживают такие большие числа, погуглите про их вместимость. Чтобы избежать такой баги, нужно или писать длинную арифметику, или, как например в этой задаче, когда нас интересует не ответ, а его остаток от деления на некоторое число, при вычислениях сразу использовать модульную арифметику (то есть в данном случае использовать то, что (a*b)mod m == ((a mod m)*(b mod m))mod m)

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Ну во-первых, нужно различать вердикты "Time Limit Exceeded" и "Wrong answer". Если первый чётко указывает, что программа работает слишком долго, то второй так же чётко указывает, что дело скорее не во времени, а в правильности.

По поводу правильности могу высказать гипотезу, что происходит переполнение типа данных в функции Power. Если возведение в степень требуется по модулю, то по этому модулю имеет смысл брать после каждого умножения. То есть i := i*i mod m и res := res*i mod m.

Удачи со сдачей этой и дальнейших задач!

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Всем спасибо! Проблема была именно в функции Power. Я ее исправил,вставив приведенный bayleef фрагмент, но что-то я не пойму,что я сделал. Не много не поясните. Вот полностью рабочий код задачи

program Project2;

{$APPTYPE CONSOLE}

var
  N,M,Y: Word;
  i: Word;
  found: Boolean;

function Power(i: Integer; N: Word; m: Word): Integer;
var res: Integer;
begin
  if odd(N) then  res:=i
  else res := 1;
  while N>1 do
  begin
    N:=N div 2;
    i:=i*i mod m;
    if odd(N) then
      res:=res*i mod m;
  end;
  Power:=res;
end;


begin
  ReadLn(N, M, Y);
  found:=true;
  for i := 0 to M - 1 do
    if Power(i, N,M) = Y then
    begin
      Write(i, ' ');
      found:=false;
    end;
  if found then Write(-1);
end.
  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Минуту вдумывался что же означает предложение "Не много не поясните." Подумал, что ты какой-нибудь китаец изучающий русский, кинув взгляд на никнейм, подумал, что вроде русский, данные в профиле это подтвердили. Оказывается это было "Немного не поясните?" или в более человеческой форме "Не поясните немного?" если предложение вопросительное, то первое "не" какбы ставит под сомнение последующую часть "Не [утверждение]". В качестве примера "Не передадите соль?" "Не много ли пафоса?". В общем русскому языку обучать не буду, но так выражаться нельзя, я мозги вывернул наизнанку чтобы понять смысл написанного.
    upd: исходное предложение заканчивается на точку, а не вопросительный взгляд, но и в той и другой форме не имеет никакого смысла.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А другого способа повыделываться, кроме как на чужой грамотности, не нашлось?

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Да мне по большому счету пофиг на грамотность, сам делаю кучу ошибок и опечаток, не уделяя этому внимания, просто я действительно долго расшифровывал что же автор имел в виду.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      вообще-то здесь не грамматика написания, а сами задачи обсуждаются... человек пишет как может, думаю, не стоит так осуждать за это! Главное всем понятно, что он имелл ввиду!