Under construction

Still being built. Things may change

Linear Congruences

Time limit1sMemory limit512 MB

Summary

Given M and b, count pairs (a, m) with 1 <= a <= M and 2 <= m <= M where ax = b (mod m) has at least one solution.

Level: Medium6 of 10
Topics: Number theory, Math, Divide and conquer
Solved: No attempts yet

Problem

Given integers $M$ and $b$ , write a program that counts the pairs $(a, m)$ that satisfy both conditions below.

Condition 1: $a$ and $m$ are integers with $1 \le a \le M$ and $2 \le m \le M$ , respectively.
Condition 2: the linear congruence $ax \equiv b \pmod m$ in $x$ has at least one solution.

Input

The first line contains integers $M$ and $b$ in this order.

Output

Print the number of pairs $(a, m)$ that satisfy the conditions.

Constraints

$2 \le M \le 2 \times 10^5$
$0 \le b \le 10^{12}$
All numbers in the input are integers.

Examples2

Example 1
Input
```
3 4
```
Expected output
```
5
```
Example 2
Input
```
5 7
```
Expected output
```
14
```

Loading...