MLLOVE - Masud and Layla love story

Masud and Layla are good friend. At the age of 20, Masud went abroad to study. That's why Layla is very disappointed. So she decided to meet with Masud as soon as possible. But Layla does not know where is Masud. So she went out to find Masud.

Layla will start looking for Masud from the 1st index. Layla know the value of n and k. Layle will go to (1+i×k)th index (where i = 0, 1, 2, 3 ... 1018) for find Masud and buy gift.

From (1+i×k)th index she will collect the gift. The price of the gift is (1+i×k) % n; ('%' means MODULO).

She will buy different priced gift. (NB: Don't buy gifts of the same price more than once.)

Laila is weak in math. So Fuad and Imran will help her to calculate the total cost of the gift.

Example:

Let's say the number n = 6 and k = 3.

Now Layla can go to (1+i×k)th index... (i = 0, 1, 2, 3, 4, 5 ... Infinity)

that's mean she will go index = 1, 4, 7, 10, 13, 16 ... Infinity. Then the cost of:

  • 1st index price is (1%6) = 1.
  • 2nd index price is (4%6) = 4.
  • 3rd index price is (7%6) = 1.
  • 4th index price is (10%6) = 4.
  • ... and so it will continue.

At the end of the process, she will collect 1 and 4 cost prices gift. So the sum of all distinct price is 5.

Input

You are given n and k, where (1 <= n <= 10^9 and 1 <= k <= 10^9).

Output

An integer number in one line. Total cost of distinct gifts.

Example

Input:
6 3

Output:
5

Added by:fuad71
Date:2022-06-20
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:No

hide comments
2022-10-30 02:04:10
Enjoyed. I'm voting this an easy Classical.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.