Задача №114684. Две люстры
Вася — владелец крупной строительной компании. Как и у всякого большого начальника у него есть большой, солидно обставленный кабинет, в котором висят две хрустальные люстры. Так сложилось, что Васе проще думать, если свет в комнате каждый день разного цвета. Когда Вася отдавал распоряжение о том, как именно оформлять его кабинет, он также указал, что ему нужны две таких люстры, чтобы в них каждый день цвет освещения изменялся по какому-нибудь циклу. Например, по такому: красный – коричневый – желтый – красный – коричневый – желтый, и так по кругу.
В продаже было несколько люстр, отличающихся друг от друга набором цветов в цикле или порядком. По какой-то ошибке, а может из-за невнимательности, человек, ответственный за выбор люстр, купил две разные люстры.
Из-за того, что люстры разные, в некоторые дни они будут светить одинаково, а в некоторые — по разному. Естественно, это не солидно, и вообще раздражает Васю, так что когда в \(k\)-й раз наступит событие «сегодня люстры светят разными цветами», Вася очень разозлится и кого-то уволит (вероятно, сотрудника, купившего люстры). Ваша задача – понять, на какой день, начиная со дня установки люстр, это случится. Считайте, что Вася очень любит работать, поэтому работает каждый день, без праздников и выходных.
В первой строке даны три целых числа \(n\), \(m\), \(k\), (\(1 \le n, m \le 500\,000\), \(1 \le k \le 10^{12}\)) — количество цветов в первой люстре, количество цветов во второй люстре и сколько раз люстры должны гореть разным цветом, чтобы Вася очень разозлился.
Во второй строке даны \(n\) различных чисел \(a_i\) (\(1 \le a_i \le 2 \cdot \max(n, m)\)), задающих последовательность цветов для первой люстры.
В третьей строке даны \(m\) различных чисел \(b_j\) (\(1 \le b_i \le 2 \cdot \max(n, m)\)), задающих последовательность цветов для второй люстры.
В \(i\)-й день первая люстра светит цветом \(a_x\), где \(x = ((i - 1) \mod n) + 1)\), а вторая цветом \(b_y\), где \(y = ((i - 1) \mod m) + 1)\).
Гарантируется, что последовательность \(a\) не совпадает тождественно с последовательностью \(b\), а значит лампы будут периодически раздражать Васю.
Выведите одно число — через сколько дней Вася очень разозлится.
В первом тесте из условия люстры будут гореть разными цветами в дни \(1\), \(2\), \(4\) и \(5\). Соответственно ответом является \(5\).
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\), \(m\) | \(k\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 15 | \(n, m\le 1000\) | \(k \le 1000\) | 0 | |
| 2 | 42 | \(n, m\le 50\,000\) | – | – | \(gcd(n, m) = 1\) |
| 3 | 19 | \(n, m\le 50\,000\) | – | 0–2 | |
| 4 | 24 | – | – | 0–3 | |
\(gcd(n, m)\) обозначает наибольший общий делитель \(n\) и \(m\)
4 2 4 4 2 3 1 2 1
5
3 8 41 1 3 2 1 6 4 3 5 7 2 8
47
1 2 31 1 1 2
62