Задача №114027. Большие числа для маленького Васи
Васе на день рождения подарили два числа.
Первое число состоит из цифры D , записанной N раз. Второе состоит из той же цифры D , записанной M раз.
Васе числа очень понравилась, и он захотел с ними поиграть. Он решил найти наибольший общий делитель этих двух чисел (как известно, наибольший общий делитель двух чисел равен наибольшему натуральному числу, на которое оба данных числа делятся без остатка). Однако ему не удалось это сделать — числа оказались слишком большими для него. Поэтому он попросил вас помочь ему.
Помогите Васе! Найдите наибольший общий делитель подаренных ему чисел.
Входные данные содержат две строки.
В первой строке записаны два целых числа, разделенные пробелом: N и M ( 1 ≤ N , M ≤ 10 18 ) — количество цифр в первом и во втором числе соответственно.
Во второй строке записано одно целое число D ( 1 ≤ D ≤ 9 ) — цифра, из которой состоят Васины числа.
Если в десятичной записи наибольшего общего делителя двух Васиных чисел не более 10 6 цифр, то необходимо вывести сам наибольший общий делитель. В противном случае нужно вывести 10 6 его последних цифр. Не следует выводить лидирующие нули.
Тесты к этой задаче состоят из четырех групп.
- Тесты 1. Тест из условия, эта группа оценивается в ноль баллов.
- Тесты 2–13. В тестах этой группы 1 ≤ N , M ≤ 16 . Эта группа оценивается в 20 баллов.
- Тесты 14–24. В тестах этой группы 1 ≤ N , M ≤ 100 . Эта группа оценивается в 30 баллов.
- В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 50 баллов.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы. Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.
1 1 1
1