Modulo Fermat's Theorem

Intuition

The brute force intuition is very straightforward. We will run a loop for 'k' from 1 to 'K,' and for this, we will create every possible case, i.e., we will take different values of x,y,z and check if it satisfies the equation or not. If it does, then we will increase the counter variable. Things will become more clear from the code.

Code

#include <bits/stdc++.h>
using namespace std;
const int MOD = (int) 1e9 + 7;

typedef long long ll;

/* This function is used to calculate power of big numbers */
ll fpow(ll n, ll k, int p = MOD)
{
    ll r = 1;
    for (; k; k >>= 1) {
       
        /* Taking MOD at necessary positions */
        if (k & 1) r = r * n % p;
        n = n * n % p;
       
    }  
    /* Returning the value */
    return r;
   
}
int solve(int M, long long K) {
   
   /* This is used to avoid certain recalculations */
   vector<int>arr(1e6 + 5);
    int res = 0;
   
    /* Looping over values of 'k'*/
    for(int i=1;i<K+1;i++)
     {
        /* Initialising first M values as 0*/
        for(int j=0;j<M;j++)
        arr[j]=0;
        for(int j=1;j<M;j++)

        arr[fpow(j, i, M)] = 1;
        int found = 0;
       
        /* Creating all possible values */
        for(int j=1;j<M;j++)
        if (arr[j]) {
            int k = (1 - j + M) % M;
           
            /* If satisfies our equation */
            if (arr[k]) {
                found = 1;
                break;
            }
        }
       
        /* Increasing the count */
        res += found;
    }
    return res;
}

int main()
{
    int M;
    long long K;
   
    /* Taking Input */
    cin>>M>>K;
    cout<<solve(M,K);
}

Input

5 4

Output

2

Complexities

Time Complexity

O(K * M), where ‘K’ and ‘M’ are given as input.

Reason:  We are first looping ‘k’ till ‘K,’ which will cost us O(K) time. Inside the loop, we are finding all possible values of x,y,x, which in the worst-case costs O(M) time. Thus, the overall time complexity to O(K) + O(M) ~ O(K * M).

Space Complexity

O(1)

Reason: We are not using any variable space.

Also see, Euclid GCD Algorithm

FAQs

1. What is Number Theory?
   The pure branch of mathematics that deals with the study of integers and integer-valued functions is known as the number theory.
    
2. What are the different parts of Number Theory?
   Number theory is a vast topic and consists of a large number of topics. Some of them are Prime numbers, Combinatorics as well as advanced topics such as Modular Exponentiation, Fermat's Little Theorem, Wilson's Theorem, Chinese Remainder Theorem, Euler Totient Function, Matrix Exponentiation, etc.
    
3. How to find the divisors of a factorial?
   Steps to find the divisors of a factorial: 
   First, find the factorial of the given number.
   Then, count the total number of divisors of the factorial.
    
4. What is modulo operation?
   After one number is divided by another, the modulo operation yields the remainder or signed remainder of the division. A modulo N is the remainder of the Euclidean division of A by N, 
    
5. What is the time complexity of modulo operation?
   Modulo or remainder operation is an O(1) operation (it's essentially just a variation on division, which takes constant time on fixed-sized numbers).

Key Takeaways

We saw how we solved the problem ‘Modulo Fermat’s Theorem', which was based on Number Theory. Some other problems that revolve around the number theory concepts are Finding Power of Factorial Divisor, Count Prime in Ranges. Now don't waste any more time and head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more. 
Till then, Happy Coding!