408682: GYM103261 I Euclid's Algorithm

Memory Limit:0 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Euclid's Algorithmtime limit per test1 secondmemory limit per test256 mebibytesinputstandard inputoutputstandard output

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} - a^{k}$$$ for every positive integer $$$a$$$.

Input

The only line contains two integers $$$d$$$ and $$$k$$$ ($$$1 \le d, k < 10^{100}$$$).

Output

Print a single integer — the largest integer that divides $$$(a+d)^{k} - a^{k}$$$ for every positive integer $$$a$$$.

ExampleInput
2 2
Output
4

加入题单

上一题 下一题 算法标签: