Skaitīt risinājumu skaitu x^2 = 1 (mod p) dotajā diapazonā
Izmēģiniet to GfG Practice 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Doti divi veseli skaitļi n un p, atrodiet x integrālo atrisinājumu skaitu 2 = 1 (mod p) slēgtajā intervālā [1 n].
Piemēri:
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 Risinājumu skaits Izmēģiniet to!
Viens vienkāršs risinājums ir iziet cauri visiem skaitļiem no 1 līdz n. Katram skaitlim pārbaudiet, vai tas atbilst vienādojumam. Mēs varam izvairīties no visa diapazona iziešanas. Ideja ir balstīta uz to, ka, ja skaitlis x apmierina vienādojumu, tad visi skaitļi formā x + i*p arī apmierina vienādojumu. Mēs šķērsojam visus skaitļus no 1 līdz p, un katram skaitlim x, kas atbilst vienādojumam, atrodam skaitļu skaitu formā x + i*p. Lai atrastu skaitu, mēs vispirms atrodam lielāko skaitli dotajam x un pēc tam pievienojam (lielākais skaitlis - x)/p rezultātam.
Zemāk ir idejas īstenošana.
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>
Izvade:
4
Laika sarežģītība: Par
Palīgtelpa: O(1)
