Count number of solutions of x ^ 2 = 1 ( mod p ) in given range | C ++ program to count number of values that satisfy x ^ 2 = 1 mod p where x lies in range [ 1 , n ] ; Initialize result ; Traverse all numbers smaller than given number p . Note that we don 't  traverse from 1 to n, but 1 to 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 ] ; The largest number in the form of x + p * i in range [ 1 , n ] ; Add count of numbers of the form x + p * i . 1 is added for x itself . ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; typedef long long ll ; int findCountOfSolutions ( int n , int p ) { ll ans = 0 ; for ( ll x = 1 ; x < p ; x ++ ) { if ( ( x * x ) % p == 1 ) { ll last = x + p * ( n / p ) ; if ( last > n ) last -= p ; ans += ( ( last - x ) / p + 1 ) ; } } return ans ; } int main ( ) { ll n = 10 , p = 5 ; printf ( " % lld STRNEWLINE " , findCountOfSolutions ( n , p ) ) ; return 0 ; }