| Codeforces Round 207 (Div. 1) |
|---|
| Закончено |
Ксюша — начинающий программист. Сегодня на паре по программированию она изучила, что такое расстояние Хемминга.
Расстоянием Хемминга между двумя строками s = s1s2... sn и t = t1t2... tn равной длины n называется величина 
. Запись [si ≠ ti] является нотацией Айверсона и обозначает: если si ≠ ti — единицу, иначе — ноль.
Теперь Ксюша хочет посчитать расстояние Хемминга между двумя длинными строками a и b. Первая строка a — это конкатенация n копий строки x, то есть 
. Вторая строка b — это конкатенация m копий строки y.
Помогите Ксюше, вычислите требуемое расстояние Хемминга по заданным n, x, m, y.
В первой строке записаны два целых числа n и m (1 ≤ n, m ≤ 1012). Во второй строке записана непустая строка x. В третьей строке записана непустая строка y. Обе строки состоят из не более чем 106 строчных букв латинского алфавита.
Гарантируется, что строки a и b, полученные по входным данным, имеют одинаковую длину.
Выведите единственное целое число — искомое расстояние Хемминга.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
100 10
a
aaaaaaaaaa
0
1 1
abacaba
abzczzz
4
2 3
rzr
az
5
В первом тестовом примере строка a равна строке b и равна 100 буквам a. Так как строки равны, расстояние Хемминга между ними равно нулю.
Во втором тестовом примере у строк a и b различаются 3-ый, 5-ый, 6-ой, и 7-ой символы. Таким образом расстояние Хемминга равно 4.
В третьем тестовом примере строка a равна rzrrzr, а строка b — azazaz. Строки отличаются во всех символах кроме 2-го, расстояние Хемминга между ними равно 5.
