Euclid’s Algorithm

양의 정수 d와 k가 주어질 때, 모든 양의 정수 a에 대해 (a+d)^k - a^k를 나누는 가장 큰 정수를 구한다.

어려움8정수론수학조합론구현아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제 설명

예제1

문제

Euclid’s algorithm is one of the oldest algorithms known to mankind. It is used to find greatest common divisor of two given numbers. Your program should also take two numbers and find a greatest common divisor. And may Euclid be with you.

I give you two positive integers d and k. Your task is to find the largest integer that divides (a + d)k − ak for every positive integer a.

입력

The only line contains two integers d and k (1 ≤ d, k < 10100).

출력

Print a single integer — the largest integer that divides (a + d)k − ak for every positive integer a.