All Tracks Math Number Theory Basic Number Theory-1 Problem

Modulo Fermat's Theorem
Tag(s):

Basic Number Theory-1, Math, Medium-Hard, Number Theory

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}\)

 

SAMPLE INPUT
5 4
SAMPLE 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\).

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), 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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?