Number of solutions to Modular Equations | C ++ Program to find number of possible values of X to satisfy A mod X = B ; Returns the number of divisors of ( A - B ) greater than B ; if N is divisible by i ; count only the divisors greater than B ; checking if a divisor isnt counted twice ; Utility function to calculate number of all possible values of X for which the modular equation holds true ; if A = B there are infinitely many solutions to equation or we say X can take infinitely many values > A . We return - 1 in this case ; if A < B , there are no possible values of X satisfying the equation ; the last case is when A > B , here we calculate the number of divisors of ( A - B ) , which are greater than B ; Wrapper function for numberOfPossibleWaysUtil ( ) ; if infinitely many solutions available ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int calculateDivisors ( int A , int B ) { int N = ( A - B ) ; int noOfDivisors = 0 ; for ( int i = 1 ; i <= sqrt ( N ) ; i ++ ) { if ( ( N % i ) == 0 ) { if ( i > B ) noOfDivisors ++ ; if ( ( N / i ) != i && ( N / i ) > B ) noOfDivisors ++ ; } } return noOfDivisors ; } int numberOfPossibleWaysUtil ( int A , int B ) { if ( A == B ) return -1 ; if ( A < B ) return 0 ; int noOfDivisors = 0 ; noOfDivisors = calculateDivisors ( A , B ) ; return noOfDivisors ; } void numberOfPossibleWays ( int A , int B ) { int noOfSolutions = numberOfPossibleWaysUtil ( A , B ) ; if ( noOfSolutions == -1 ) { cout << " For ▁ A ▁ = ▁ " << A << " ▁ and ▁ B ▁ = ▁ " << B << " , ▁ X ▁ can ▁ take ▁ Infinitely ▁ many ▁ values " " ▁ greater ▁ than ▁ " << A << " STRNEWLINE " ; } else { cout << " For ▁ A ▁ = ▁ " << A << " ▁ and ▁ B ▁ = ▁ " << B << " , ▁ X ▁ can ▁ take ▁ " << noOfSolutions << " ▁ values STRNEWLINE " ; } } int main ( ) { int A = 26 , B = 2 ; numberOfPossibleWays ( A , B ) ; A = 21 , B = 5 ; numberOfPossibleWays ( A , B ) ; return 0 ; }