Tel het aantal oplossingen van x ^ 2 = 1 (mod p) binnen een bepaald bereik
Probeer het eens op GfG Practice 
#practiceLinkDiv {weergave: geen! belangrijk; }
#practiceLinkDiv {weergave: geen! belangrijk; } Gegeven twee gehele getallen n en p, vind het aantal integrale oplossingen voor x 2 = 1 (mod p) in het gesloten interval [1 n].
Voorbeelden:
Input : n = 10 p = 5 Output : 4 There are four integers that satisfy the equation x 2 = 1. The numbers are 1 4 6 and 9. Input : n = 15 p = 7 Output : 5 There are five integers that satisfy the equation x 2 = 1. The numbers are 1 8 15 6 and 13.Recommended Practice Aantal oplossingen Probeer het!
Een eenvoudige oplossing is om alle getallen van 1 tot n door te nemen. Controleer voor elk getal of het aan de vergelijking voldoet. We kunnen voorkomen dat we het hele bereik doornemen. Het idee is gebaseerd op het feit dat als een getal x aan de vergelijking voldoet, alle getallen van de vorm x + i*p ook aan de vergelijking voldoen. We doorkruisen alle getallen van 1 tot p en voor elk getal x dat aan de vergelijking voldoet, vinden we het aantal getallen van de vorm x + i*p. Om de telling te vinden, vinden we eerst het grootste getal voor gegeven x en voegen dan (grootste getal - x)/p toe aan het resultaat.
Hieronder vindt u de implementatie van het idee.
C++ // C++ program to count number of values // that satisfy x^2 = 1 mod p where x lies // in range [1 n] #include 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 [1n] 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 [1n] 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 [1n] 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 [1n] 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 // 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 [1n] 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 [1n] 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>
Uitgang:
4
Tijdcomplexiteit: Over
Hulpruimte: O(1)
