home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

นับจำนวนคำตอบของ x^2 =1 (mod p) ในช่วงที่กำหนดใน C++

เราได้รับด้วยจำนวนเต็ม x และ p เป้าหมายคือการหาจำนวนคำตอบของสมการ −x 2 =1 ( mod p ) โดยที่ x อยู่ในช่วง [1,N].

เราจะทำสิ่งนี้โดยข้ามจาก 1 ถึง N และนำแต่ละตัวเลขมาตรวจสอบว่า (x*x)%p==1 หรือไม่ ถ้าใช่ ให้เพิ่มจำนวนขึ้น

มาทำความเข้าใจกับตัวอย่างกัน

ป้อนข้อมูล − n=5, p=2

ผลผลิต − จำนวนโซลูชั่น − 3

คำอธิบาย − ระหว่างช่วง 1 ถึง 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.

ป้อนข้อมูล − n=3, p=4

ผลผลิต − จำนวนโซลูชั่น − 2

คำอธิบาย − ระหว่างช่วง 1 ถึง 3

12=1%4=1, count=1
22=4%4=0, count=1
32=9%4=1, count=2
Total number of solutions=2

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

  • เราใช้สองตัวแปร n และ p.

  • ฟังก์ชั่น solutionsCount(int n,int p) รับทั้งพารามิเตอร์ n และ p และส่งกลับจำนวนคำตอบสำหรับสมการ:x 2 %p==1 (หรือ x 2 =1 ( mod p ) )

  • เริ่มจาก x=1 ถึง x=n ตรวจสอบว่า x*x==1 หรือไม่ ถ้าใช่ ให้นับจำนวนที่เพิ่มขึ้น

  • ในตอนท้ายของลูป การนับ จะมีจำนวนคำตอบ

  • ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

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

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Number of solutions : 6