Number of solutions to Modular Equations | Python 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
import math NEW_LINE def calculateDivisors ( A , B ) : NEW_LINE INDENT N = A - B NEW_LINE noOfDivisors = 0 NEW_LINE a = math . sqrt ( N ) NEW_LINE for i in range ( 1 , int ( a + 1 ) ) : NEW_LINE INDENT if ( ( N % i == 0 ) ) : NEW_LINE INDENT if ( i > B ) : NEW_LINE INDENT noOfDivisors += 1 NEW_LINE DEDENT if ( ( N / i ) != i and ( N / i ) > B ) : NEW_LINE INDENT noOfDivisors += 1 ; NEW_LINE DEDENT DEDENT DEDENT return noOfDivisors NEW_LINE DEDENT def numberOfPossibleWaysUtil ( A , B ) : NEW_LINE INDENT if ( A == B ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT if ( A < B ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT noOfDivisors = 0 NEW_LINE noOfDivisors = calculateDivisors ; NEW_LINE return noOfDivisors NEW_LINE DEDENT def numberOfPossibleWays ( A , B ) : NEW_LINE INDENT noOfSolutions = numberOfPossibleWaysUtil ( A , B ) NEW_LINE if ( noOfSolutions == - 1 ) : NEW_LINE INDENT print ( " For ▁ A ▁ = ▁ " , A , " ▁ and ▁ B ▁ = ▁ " , B , " , ▁ X ▁ can ▁ take ▁ Infinitely ▁ many ▁ values " , " ▁ greater ▁ than ▁ " , A ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " For ▁ A ▁ = ▁ " , A , " ▁ and ▁ B ▁ = ▁ " , B , " , ▁ X ▁ can ▁ take ▁ " , noOfSolutions , " ▁ values " ) NEW_LINE DEDENT DEDENT A = 26 NEW_LINE B = 2 NEW_LINE numberOfPossibleWays ( A , B ) NEW_LINE A = 21 NEW_LINE B = 5 NEW_LINE numberOfPossibleWays ( A , B ) NEW_LINE