Тема: Codefoces 17
Спасибо, Егор, за интересные задачи. 
все-таки интересно - Максиму повезло (слабость тестов) что его a^(b%phi(с))%c для a и c не взаимно простых прокатило или все-таки можно и для них ?
Re: Codefoces 17
Ну я говорю, мне показалось, что это происходит, только когда b >= phi(c), и мне показалось, что неверный ответ получается, только когда a^phi(c) == 0 (типа взятием по модулю phi(c) мы отбрасываем несколько циклов, но это неправильно, если каждый цикл давал 0).
Не знаю, я и сам не могу это обосновать никак.
Но надо признать, что это я придумал не на контесте, а сдавал подобную задачу ранее, и там точно такой же метод прошёл.
Re: Codefoces 17
Oleg пишет:
Спасибо, Егор, за интересные задачи.
все-таки интересно - Максиму повезло (слабость тестов) что его a^(b%phi(с))%c для a и c не взаимно простых прокатило или все-таки можно и для них ?
На самом деле это естественно не верно для не взаимно простых, но если сделать степень минимальной больше где-то log2(n),то это работает! Обоснование читать в разборе ^_^ Не знаю, вроде тесты делались для похожих решений