logo

TechCodeview

주어진 범위에서 x^2 = 1(mod p)의 해 개수 계산

GfG Practice에서 사용해 보세요. ' title= #practiceLinkDiv { 표시: 없음 !중요; }

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

예:  

Input : n = 10 p = 5 Output : 4 There are four integers that satisfy the equation x2 = 1. The numbers are 1 4 6 and 9. Input : n = 15 p = 7 Output : 5 There are five integers that satisfy the equation x2 = 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('%lldn' 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>

산출:  

4

시간 복잡도: 에 대한

보조 공간: 오(1)
 

퀴즈 만들기