Verilen aralıkta x^2 = 1 (mod p) çözümlerinin sayısını sayın
GfG Practice'de deneyin 
#practiceLinkDiv { görüntü: yok !önemli; }
#practiceLinkDiv { görüntü: yok !önemli; } Verilen iki tamsayı n ve p olduğundan x'in integral çözümlerinin sayısını bulun 2 = 1 (mod p) kapalı aralıkta [1 n].
Örnekler:
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 Çözüm sayısı Deneyin!
Basit bir çözüm, 1'den n'ye kadar tüm sayıların üzerinden geçmektir. Her sayının denklemi karşılayıp karşılamadığını kontrol edin. Tüm aralığın üzerinden geçmekten kaçınabiliriz. Fikir, eğer bir x sayısı denklemi sağlıyorsa, x + i*p formundaki tüm sayıların da denklemi sağladığı gerçeğine dayanmaktadır. 1'den p'ye kadar tüm sayılar için çapraz geçiş yaparız ve denklemi karşılayan her x sayısı için x + i*p formundaki sayıların sayısını buluruz. Sayımı bulmak için önce verilen x için en büyük sayıyı buluruz ve sonra sonuca (en büyük sayı - x)/p'yi ekleriz.
Aşağıda fikrin uygulanması yer almaktadır.
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>
Çıkış:
4
Zaman Karmaşıklığı: Hakkında
Yardımcı Alan: Ç(1)
