Дамы и Господа! Нужна Ваша помощь. Решил заняться олимпиадным программированием и вот пока встречаю камни предкновения. Решал задачу с 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 тесте. Предполагаю не укладывается по времени, но я уже не знаю как ее еще улучшить. Помогите кто чем сможет
Валится не по времени, а из-за неправильного ответа(если ваш тимусовский ник, конечно, Artem)
Проблема в том, что когда вы возносите число X в степень N, оно может быть достаточно большим(998^998). Стандартные типы данных не поддерживают такие большие числа, погуглите про их вместимость. Чтобы избежать такой баги, нужно или писать длинную арифметику, или, как например в этой задаче, когда нас интересует не ответ, а его остаток от деления на некоторое число, при вычислениях сразу использовать модульную арифметику (то есть в данном случае использовать то, что (a*b)mod m == ((a mod m)*(b mod m))mod m)
Ну во-первых, нужно различать вердикты "Time Limit Exceeded" и "Wrong answer". Если первый чётко указывает, что программа работает слишком долго, то второй так же чётко указывает, что дело скорее не во времени, а в правильности.
По поводу правильности могу высказать гипотезу, что происходит переполнение типа данных в функции Power. Если возведение в степень требуется по модулю, то по этому модулю имеет смысл брать после каждого умножения. То есть i := i*i mod m и res := res*i mod m.
Удачи со сдачей этой и дальнейших задач!
Всем спасибо! Проблема была именно в функции Power. Я ее исправил,вставив приведенный bayleef фрагмент, но что-то я не пойму,что я сделал. Не много не поясните. Вот полностью рабочий код задачи
Минуту вдумывался что же означает предложение "Не много не поясните." Подумал, что ты какой-нибудь китаец изучающий русский, кинув взгляд на никнейм, подумал, что вроде русский, данные в профиле это подтвердили. Оказывается это было "Немного не поясните?" или в более человеческой форме "Не поясните немного?" если предложение вопросительное, то первое "не" какбы ставит под сомнение последующую часть "Не [утверждение]". В качестве примера "Не передадите соль?" "Не много ли пафоса?". В общем русскому языку обучать не буду, но так выражаться нельзя, я мозги вывернул наизнанку чтобы понять смысл написанного.
upd: исходное предложение заканчивается на точку, а не вопросительный взгляд, но и в той и другой форме не имеет никакого смысла.
А другого способа повыделываться, кроме как на чужой грамотности, не нашлось?
Да мне по большому счету пофиг на грамотность, сам делаю кучу ошибок и опечаток, не уделяя этому внимания, просто я действительно долго расшифровывал что же автор имел в виду.
вообще-то здесь не грамматика написания, а сами задачи обсуждаются... человек пишет как может, думаю, не стоит так осуждать за это! Главное всем понятно, что он имелл ввиду!