주어진 범위에서 X^2 = 1(MOD P)의 해 개수 계산

GfG Practice에서 사용해 보세요.

#practiceLinkDiv { 표시: 없음 !중요; }

두 개의 정수 n과 p가 주어지면 x에 대한 적분 해의 수를 찾습니다. ²닫힌 구간 [1 n]에서 = 1 (mod p)입니다.

예:

Input : n = 10 p = 5 Output : 4 There are four integers that satisfy the equation x ² = 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 ² = 1. The numbers are 1 8 15 6 and 13.

Recommended Practice 솔루션 수 시도해 보세요!

한 가지 간단한 해결책은 1부터 n까지의 모든 숫자를 살펴보는 것입니다. 모든 숫자에 대해 방정식을 만족하는지 확인하세요. 우리는 전체 범위를 통과하는 것을 피할 수 있습니다. 이 아이디어는 숫자 x가 방정식을 충족하면 x + i*p 형식의 모든 숫자도 방정식을 충족한다는 사실에 기초합니다. 우리는 1부터 p까지 모든 숫자를 탐색하고 방정식을 만족하는 모든 숫자 x에 대해 x + i*p 형식의 숫자 개수를 찾습니다. 개수를 찾으려면 먼저 주어진 x에 대해 가장 큰 숫자를 찾은 다음 결과에 (가장 큰 숫자 - x)/p를 추가합니다.

아래는 아이디어의 구현입니다.

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# 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>