GCD and Shortest Path

Time limit1sMemory limit1024 MB

Summary

Count the vertices x from 1 to N whose shortest-path distance to K in the coprime graph equals gcd(x, K).

Level: Medium7 of 10
Topics: Number theory, Graph, Math
Solved: No attempts yet

Problem

$\newcommand{\dist}{\mathrm{dist}}$

A graph with $N$ vertices, numbered from $1$ to $N$ , is given. The graph has the following property.

For two distinct integers $x, y$ that satisfy $1 \leq x, y \leq N$ :

If $\gcd(x, y) = 1$ , an edge connects vertex $x$ and vertex $y$ .
If $\gcd(x, y) \neq 1$ , no edge connects vertex $x$ and vertex $y$ .

Define $\dist(x, y)$ as the length of the shortest path between vertex $x$ and vertex $y$ . If no path connects the two vertices, define $\dist(x, y) = 10^{10^{10}}$ . By definition, $\dist(x, x) = 0$ .

Given an integer $K$ with $1 \leq K \leq N$ , count the integers $x$ with $1 \leq x \leq N$ that satisfy $\dist(x, K) = \gcd(x, K)$ .

Input

Print the first line with the integer $K$ and the integer $N$ , separated by a space. ( $1 \leq K \leq N \leq 10^6$ )

Output

On the first line, print the number of integers that satisfy the condition.

Hint

$\gcd(x, y)$ is the greatest common divisor of $x$ and $y$ .

The length of a path is the number of edges it contains. The length of the shortest path is the minimum of these lengths.

Examples4

Example 1
Input
```
3 4
```
Expected output
```
3
```
Example 2
Input
```
6 20
```
Expected output
```
14
```
Example 3
Input
```
2 3
```
Expected output
```
2
```
Example 4
Input
```
1 1
```
Expected output
```
0
```