Count number of solutions of x^2 = 1 (mod p) in given range
Given two integers n and p, find the number of integral solutions to x2 = 1 (mod p) in the closed interval [1, n].
Examples:
Input : n = 10, p = 5 Output : 4 There are four integers that satisfy the equation x2 = 1. The numbers are 1, 4, 6 and 9. Input : n = 15, p = 7 Output : 5 There are five integers that satisfy the equation x2 = 1. The numbers are 1, 8, 15, 6 and 13.
One simple solution is to go through all numbers from 1 to n. For every number, check if it satisfies the equation. We can avoid going through the whole range. The idea is based on the fact that if a number x satisfies the equation, then all numbers of the form x + i*p also satisfy the equation. We traverse for all numbers from 1 to p and for every number x that satisfies the equation, we find the count of numbers of the form x + i*p. To find the count, we first find the largest number for given x and then add (largest-number – x)/p to the result.
Below is the implementation of the idea.
C++
// C++ program to count number of values // that satisfy x^2 = 1 mod p where x lies // in range [1, n] #include<bits/stdc++.h> using namespace std; typedef long long ll; int findCountOfSolutions( int n, int p) { // Initialize result ll ans = 0; // Traverse all numbers smaller than // given number p. Note that we don't // traverse from 1 to n, but 1 to p for (ll x=1; x<p; x++) { // If x is a solution, then count all // numbers of the form x + i*p such // that x + i*p is in range [1,n] if ((x*x)%p == 1) { // The largest number in the // form of x + p*i in range // [1, n] ll last = x + p * (n/p); if (last > n) last -= p; // Add count of numbers of the form // x + p*i. 1 is added for x itself. ans += ((last-x)/p + 1); } } return ans; } // Driver code int main() { ll n = 10, p = 5; printf ( "%lld\n" , findCountOfSolutions(n, p)); return 0; } |
Java
// Java program to count // number of values that // satisfy x^2 = 1 mod p // where x lies in range [1, n] import java.io.*; class GFG { static int findCountOfSolutions( int n, int p) { // Initialize result int ans = 0 ; // Traverse all numbers // smaller than given // number p. Note that // we don't traverse from // 1 to n, but 1 to p for ( int x = 1 ; x < p; x++) { // If x is a solution, // then count all numbers // of the form x + i*p // such that x + i*p is // in range [1,n] if ((x * x) % p == 1 ) { // The largest number // in the form of x + // p*i in range [1, n] int last = x + p * (n / p); if (last > n) last -= p; // Add count of numbers // of the form x + p*i. // 1 is added for x itself. ans += ((last - x) / p + 1 ); } } return ans; } // Driver code public static void main (String[] args) { int n = 10 ; int p = 5 ; System.out.println( findCountOfSolutions(n, p)); } } // This code is contributed by ajit |
Python3
# Program to count number of # values that satisfy x^2 = 1 # mod p where x lies in range [1, n] def findCountOfSolutions(n, p): # Initialize result ans = 0 ; # Traverse all numbers smaller # than given number p. Note # that we don't traverse from # 1 to n, but 1 to p for x in range ( 1 , p): # If x is a solution, then # count all numbers of the # form x + i*p such that # x + i*p is in range [1,n] if ((x * x) % p = = 1 ): # The largest number in the # form of x + p*i in range # [1, n] last = x + p * (n / p); if (last > n): last - = p; # Add count of numbers of # the form x + p*i. 1 is # added for x itself. ans + = ((last - x) / p + 1 ); return int (ans); # Driver code n = 10 ; p = 5 ; print (findCountOfSolutions(n, p)); # This code is contributed by mits |
C#
// C# program to count // number of values that // satisfy x^2 = 1 mod p // where x lies in range [1, n] using System; class GFG { static int findCountOfSolutions( int n, int p) { // Initialize result int ans = 0; // Traverse all numbers // smaller than given // number p. Note that // we don't traverse from // 1 to n, but 1 to p for ( int x = 1; x < p; x++) { // If x is a solution, // then count all numbers // of the form x + i*p // such that x + i*p is // in range [1,n] if ((x * x) % p == 1) { // The largest number // in the form of x + // p*i in range [1, n] int last = x + p * (n / p); if (last > n) last -= p; // Add count of numbers // of the form x + p*i. // 1 is added for x itself. ans += ((last - x) / p + 1); } } return ans; } // Driver code static public void Main () { int n = 10; int p = 5; Console.WriteLine( findCountOfSolutions(n, p)); } } // This code is contributed by ajit |
PHP
<?php // Program to count number of // values that satisfy x^2 = 1 // mod p where x lies in range [1, n] function findCountOfSolutions( $n , $p ) { // Initialize result $ans = 0; // Traverse all numbers smaller // than given number p. Note // that we don't traverse from // 1 to n, but 1 to p for ( $x = 1; $x < $p ; $x ++) { // If x is a solution, then // count all numbers of the // form x + i*p such that // x + i*p is in range [1,n] if (( $x * $x ) % $p == 1) { // The largest number in the // form of x + p*i in range // [1, n] $last = $x + $p * ( $n / $p ); if ( $last > $n ) $last -= $p ; // Add count of numbers of // the form x + p*i. 1 is // added for x itself. $ans += (( $last - $x ) / $p + 1); } } return $ans ; } // Driver code $n = 10; $p = 5; echo findCountOfSolutions( $n , $p ); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to count number // of values that satisfy x^2 = 1 mod p // where x lies in range [1, n] function findCountOfSolutions(n, p) { // Initialize result let ans = 0; // Traverse all numbers smaller // than given number p. Note that // we don't traverse from 1 to n, // but 1 to p for (let x = 1; x < p; x++) { // If x is a solution, // then count all numbers // of the form x + i*p // such that x + i*p is // in range [1,n] if ((x * x) % p == 1) { // The largest number // in the form of x + // p*i in range [1, n] let last = x + p * (n / p); if (last > n) last -= p; // Add count of numbers // of the form x + p*i. // 1 is added for x itself. ans += ((last - x) / p + 1); } } return ans; } // Driver code let n = 10; let p = 5; document.write(findCountOfSolutions(n, p)); // This code is contributed by susmitakundugoaldanga </script> |
Output:
4
Time Complexity: O(p)
Auxiliary Space: O(1)