Chúng ta được cho với các số nguyên x và p. Mục đích là tìm số nghiệm của phương trình −x 2 =1 (mod p) sao cho x nằm trong khoảng [1, N].
Chúng ta sẽ thực hiện điều này bằng cách chuyển từ 1 đến N và lấy từng số dưới dạng x, kiểm tra xem (x * x)% p ==1. Nếu có thì hãy tăng số lượng.
Hãy cùng hiểu với các ví dụ.
Đầu vào - n =5, p =2
Đầu ra - Số lượng giải pháp - 3
Giải thích - Trong khoảng từ 1 đến 5.
12=1%2=1, count=1 22=4%2=0, count=1 32=9%2=1, count=2 42=16%2=0, count=2 52=25%2=1, count=3 Total number of solutions=3.
Đầu vào - n =3, p =4
Đầu ra - Số lượng giải pháp - 2
Giải thích - Trong khoảng từ 1 đến 3.
12=1%4=1, count=1 22=4%4=0, count=1 32=9%4=1, count=2 Total number of solutions=2
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng ta lấy hai biến n và p.
-
Hàm giải phápCount (int n, int p) nhận cả hai tham số n và p và trả về số nghiệm cho phương trình:x 2 % p ==1 (hoặc x 2 =1 (mod p)).
-
Bắt đầu từ x =1 đến x =n, hãy kiểm tra xem x * x ==1, nếu có thì số gia tăng.
-
Ở cuối vòng lặp, đếm sẽ có số giải pháp.
-
Kết quả là số lượt trả lại.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
int solutionsCount(int n, int p){
int count = 0;
for (int x=1; x<=n; x++){
if ((x*x)%p == 1)
{ ++count; }
}
return count;
}
int main(){
int n = 8, p = 3;
cout<<"Number of solutions :"<<solutionsCount(n, p);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Number of solutions : 6