All Tracks Math Number Theory Problem
SOLVE
LATER
Modulo Fermat's Theorem
Problem
Editorial
Analytics
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}\)
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\).
Time Limit:
1.0 sec(s)
for each input file.
Memory Limit:
256 MB
Source Limit:
1024 KB
Marking Scheme:
Marks are awarded when all the testcases pass.
Allowed Languages:
Bash,
C,
C++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
TypeScript,
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Swift-4.1,
Visual Basic
CODE EDITOR
Initializing Code Editor...
Contributor
This Problem was Asked in
OTHER PROBLEMS OF THIS CHALLENGE
-
Math > Basic Geometry
-
Math > Counting
-
Algorithms > Graphs
-
Algorithms > Searching
-
Algorithms > Searching
