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

ได้รับจำนวนเต็ม n และ p ต้องการนับจำนวนคำตอบของสมการ x² ≡ 1 (mod p) โดย x อยู่ในช่วง [1, n]

ตัวอย่าง

อินพุต: n = 5, p = 2

เอาต์พุต: 3

คำอธิบาย: x=1,3,5 ให้ x²%2=1

อินพุต: n = 3, p = 4

เอาต์พุต: 2

คำอธิบาย: x=1,3 ให้ x²%4=1

แนวทาง

• วนลูป x = 1 ถึง n
• ถ้า (x*x) % p == 1 เพิ่มตัวนับ

ตัวอย่างโค้ด C++

#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