Counting Connected Graphs

There are \(m+1\) undirected graphs numbered from \(0\) to \(m\). Each graph has a fixed vertex set \(V\) of \(n\) vertices numbered from \(0\) to \(n-1\), and initially no edges exist in any graph.

For each graph with index \(x\) (where \(0 \le x \le m\)), for every vertex \(i\) with \(0 \le i \le n-1\), an undirected edge is added between vertex \(i\) and vertex \( (i \cdot x) \bmod n \). In other words, the edge set for graph \(x\) is \[ E_x = \{\{i, (i\cdot x) \bmod n\}: 0 \le i \le n-1\}\].

A graph is said to be connected if for any two distinct vertices \(u\) and \(v\) there exists a path connecting them.

Your task is to determine how many of the \(m+1\) graphs are connected.

Observation and Analysis

For a fixed \(x\), observe that for every vertex \(i\), the edge \(\{i, (i \cdot x) \bmod n\}\) has one endpoint equal to \(i\) and the other equal to \((i \cdot x) \bmod n\). In particular, note that when \(x = 0\), every vertex \(i > 0\) gets connected to vertex \(0\) (since \((i \cdot 0) \bmod n = 0\)), yielding a star graph that is connected. For any nonzero \(x\), it turns out that only when \(n \mid x\) does there exist at least one nontrivial edge that connects vertex \(0\) with other vertices in such a way that the entire graph becomes connected. In fact, one can prove that for \(x \neq 0\), the graph is connected if and only if \(n \mid x\).

Thus the number of connected graphs is exactly the number of \(x\) in \(\{0,1,2,\dots,m\}\) satisfying \(x = 0\) or \(n \mid x\). Equivalently, this equals the number of multiples of \(n\) between \(0\) and \(m\) (inclusive). Note that \(0\) is a multiple of every number. Therefore, the answer is:

[ \text{answer} = \left\lfloor \frac{m}{n} \right\rfloor + 1. ]

It is guaranteed that \(n \ge 2\), so when \(m .

inputFormat

The input consists of a single line containing two integers \(n\) and \(m\) \((2 \le n \le 10^9,\; 0 \le m \le 10^{12})\), where \(n\) is the number of vertices and \(m\) defines that there are \(m+1\) graphs, with indices \(0\) through \(m\).

outputFormat

Output a single integer, the number of connected graphs among the \(m+1\) graphs.

sample

6 5

1