Modulo Fermat's Theorem
Math
Medium
Number theory
Number theory
37.0% success
6,282 attempts
1s time
256MB memory
1024KB max code
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}\)
Examples
Input
5 4
Output
2
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\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Loading Editor...