Большие числа для маленького Васи
시간 제한1초메모리 제한1024 MB
같은 숫자 D를 N번 이어 붙인 수와 M번 이어 붙인 수의 최대공약수를 구하고, 자릿수가 10^6을 넘으면 마지막 10^6자리만 출력한다.
문제
Васе на день рождения подарили два числа.
Первое число состоит из цифры D, записанной N раз. Второе состоит из той же цифры D, записанной M раз.
Васе числа очень понравилась, и он захотел с ними поиграть. Он решил найти наибольший общий делитель этих двух чисел (как известно, наибольший общий делитель двух чисел равен наибольшему натуральному числу, на которое оба данных числа делятся без остатка). Однако ему не удалось это сделать — числа оказались слишком большими для него. Поэтому он попросил вас помочь ему.
Помогите Васе! Найдите наибольший общий делитель подаренных ему чисел.
입력
Входные данные содержат две строки.
В первой строке записаны два целых числа, разделенные пробелом: N и M (1 ⩽ N, M ⩽ 1018) — количество цифр в первом и во втором числе соответственно.
Во второй строке записано одно целое число D (1 ⩽ D ⩽ 9) — цифра, из которой состоят Васины числа.
출력
Если в десятичной записи наибольшего общего делителя двух Васиных чисел не более 106 цифр, то необходимо вывести сам наибольший общий делитель. В противном случае нужно вывести 106 его последних цифр. Не следует выводить лидирующие нули.