thank you! :)
changed!

If you only registered to write comments like this one, it'd be better if you didn't at all.

While TC has a smaller variety of problems and weird restrictions (which sometimes lead to a lot of unnecessary input parsing), and the contests are done using a fail Java arena (I've never been able to log in when using a proxy server in Slovakia), the problems are often interesting and it has other well done features on the site, like algorithm tutorials. It's still worth competing.

Ну мне не хватило 30 секунд на перебором сгенерировать ответ для маленьких и решить систему урвенений на коэффициенты при n*m, n*m/g, n*m/(g*g), n, m, n/g, m/g, (n/g)%2, (m/g)%2, 1. Оно решается и получается что-то очень простое. В practice прошло.

P.S. g = gcd(n,m); n это 2*n-2 исходное; m это 2*m-2 исходное. На самом деле из этого всего нужно только n*m/g, n*m/(g^2), n/g, m/g, 1. Но это как-то не очевидно.

Как я решал (сдал правда после контеста): Будем решать немного по-другому сформулированую задачу. Пускай есть бильярдный стол размером N-1 на M-1. Из одного из углов вылетает шар. Шар отбивается от сторон стола. Нужно определить во скольких точках с целочисельными координатами побывает шар.

Сначала найдем количество отрезков типа нижняя часть — верхняя часть. То есть, сколько раз шар пройдет путь от нижнего края к верхнему. Пускай таких отрезков X. X = НОК(N-1, M-1) / (M-1). (M < N) Тогда количество точек будет X * (M — 1) + 1 (каждый по M — 1 точке + стартовая) Теперь нужно убрать точки пересечения отрезков. Каждая из таких посчитана дважды. Найдем число Z = ceil(N / M) — сколько отрезков после вылета шар пройдет до первого пересекающегося отрезка. И запомним точку в которой он окажется. Теперь запустим цикл (пока не придумал как его превратить в формулу): На каждой отерации смотрим, если шар из данной позиции пролетит Z отрезков и при том перед ударом об боковую стенку будет лететь снизу, то отнимаем от ответа Z * номер итерации (номер итерации — это по сколько точек пересечение будет имет каждый из отрезков текущей итерации), иначе отнимием (Z — 1) * номер отерации ( так как последний раз он летел сверху перед ударом об боковую, то на последнем отрезке он пересечет количество отрезков, равное текучей итерации, иначе — уже не единицу больше — что мы и учтем на следующей итерации). И не забудем обновить текущую позицию. И так пока все отрезки не рассмотрим.

Если кто разберется, что я здесь написал, скажите, правильное ли решение (а то ТС пишет, что "Problem successfully submited for ... points", а я так и не понимаю, значить ли это АС, или же просто это успешная отправка.

UPD. Понял как на системных тестах проганять — один ТЛ, остальное — АС. То есть осталось только с циклом разобратся... code

Я могу рассказать как предполагалось её решать.

Во-первых, как уже предложил Witalia, представим задачу в виде "есть поле N x M, из угла вылетает шарик/слон и бегает, отталкиваясь от сторон; посчитать кол-во различных клеток". Опытным путем можно увидеть красивые паттерны посещаемых клеток. Например, вот какие клетки будут посещены на поле 19 x 16:

X.....X.....X.....X
.X...X.X...X.X...X.
..X.X...X.X...X.X..
...X.....X.....X...
..X.X...X.X...X.X..
.X...X.X...X.X...X.
X.....X.....X.....X
.X...X.X...X.X...X.
..X.X...X.X...X.X..
...X.....X.....X...
..X.X...X.X...X.X..
.X...X.X...X.X...X.
X.....X.....X.....X
.X...X.X...X.X...X.
..X.X...X.X...X.X..
...X.....X.....X...

Паттерн заключается в том, что поле поделится на ромбики, полуромбики и четвертьромбики с "радиусом" равным gcd(N-1, M-1). Думаю, после этого наблюдения можно решать кучей способов. Я предлагал считать сколько у нас будет фигур каждого типа и вычитать их суммарную площадь из NM. rng_58 предложил делать ещё проще. Для иллюстрации возьмём поле 11 x 16 и пометим все клетки, чьи координаты делятся на gcd(N-1, M-1)=5:

Y....Y....Y....Y
.X.......X.X....
..X.....X...X...
...X...X.....X..
....X.X.......X.
Y....Y....Y....Y
....X.X.......X.
...X...X.....X..
..X.....X...X...
.X.......X.X....
Y....Y....Y....Y

Для вычисления ответа нам нужно посчитать, сколько всего на поле Y-ов, сколько из них мы посетим и сколько осталось X-ов.

Ну круто, только главное — это не красивее решить, а побыстрее сдать. Вот все и кодили то, что первое в голову приходило.

I am surprised to see that people question additional 25 points for easy and do not complain about a 500-pointer solved by 19 people only :)

The easy seemed a bit trickier than an average d1-easy, so its point value was raised. It turned out the other way.