Modulo Fermat's Theorem

★★★★★

26 votes

Math, Medium, Number Theory, Number theory

Details

Problem

It is well-known that the equation: $x^k + y^k = z^k$ has no positive solution for $k \ge 3$ . But what if we consider solution over a finite field. Now, the task you are given is related to that:

Given a prime $P$ , you are asked to count the number of positive integers $k$ doesn't exceed $L$ s.t. modulo equation $x^k + y^k = z^k\ (modulo\ P)$ has solution $0 < x, y, z < P$ .

Input Format

A line contains two space-separated integers $P, L$ as described above.

Output Format

Output answer in a single line.

Constraints

$1 \le P \le 10^6$
$1 \le L \le 10^{18}$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Let's enumerate all possible values of $k$ :

$k = 1:$ there is a solution $(x, y, z) = (1, 1, 2)$ .
$k = 2:$ there is no solution.
$k = 3:$ this is a solution $(x, y, z) = (1, 3, 2)$ .
$k = 4:$ there is no solution.

So, answer is $2$ .