Đếm nghiệm của x² ≡ 1 (mod p) trong khoảng [1, N] C++

Cho N và p. Đếm số nguyên x ∈ [1, N] thỏa mãn x² ≡ 1 (mod p), tức là (x²) % p = 1.

Ví dụ minh họa

Ví dụ 1:

• Input: n = 5, p = 2
• Output: 3
• Giải thích: x=1: 1%2=1 ✓; x=2: 4%2=0 ✗; x=3: 9%2=1 ✓; x=4: 16%2=0 ✗; x=5: 25%2=1 ✓. Tổng 3 nghiệm.

Ví dụ 2:

• Input: n = 3, p = 4
• Output: 2
• Giải thích: x=1: 1%4=1 ✓; x=2: 4%4=0 ✗; x=3: 9%4=1 ✓.

Mã nguồn C++ (Duyệt tuần tự)

#include <bits/stdc++.h>
using namespace std;

int solutionsCount(int n, int p) {
    int count = 0;
    for (int x = 1; x <= n; x++) {
        if ((1LL * x * x) % p == 1) count++;
    }
    return count;
}

int main() {
    int n = 8, p = 3;
    cout << "So nghiem: " << solutionsCount(n, p);
    return 0;
}

Kết quả chạy chương trình

So nghiem: 6

Phân tích toán học (Tối ưu cho N, p lớn)

Phương trình x² ≡ 1 (mod p) ⇔ (x-1)(x+1) ≡ 0 (mod p).

Trường hợp p là số nguyên tố

Chỉ có 2 nghiệm modulo p: x ≡ 1 (mod p) và x ≡ -1 ≡ p-1 (mod p).

Số nghiệm trong [1, N] = ⌊(N-1)/p⌋ + 1 + ⌊(N-(p-1))/p⌋ + 1 (nếu p>2).

Trường hợp p hợp thành

Phân tích p = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ.

Số nghiệm modulo p = tích số nghiệm modulo từng pᵢ^eᵢ (theo Định lý Dư Trung Hoa).

• pᵢ lẻ: 2 nghiệm modulo pᵢ^eᵢ (±1)
• pᵢ = 2:
  • e=1 (mod 2): 1 nghiệm (1)
  • e=2 (mod 4): 2 nghiệm (1, 3)
  • e≥3 (mod 2^e): 4 nghiệm (±1, ±1+2^(e-1))

Mã nguồn tối ưu O(√p + k) - Tìm nghiệm modulo p rồi đếm

#include <bits/stdc++.h>
using namespace std;

vector findSolutionsModP(int p) {
    vector sols;
    for (int x = 0; x < p; x++) {
        if ((1LL * x * x) % p == 1) sols.push_back(x);
    }
    return sols;
}

long long countSolutionsOptimized(long long N, int p) {
    vector sols = findSolutionsModP(p);
    long long count = 0;
    for (int r : sols) {
        if (r == 0) continue; // x ∈ [1, N]
        // Số x ≡ r (mod p) trong [1, N]
        if (r > N) continue;
        count += (N - r) / p + 1;
    }
    return count;
}

int main() {
    cout << countSolutionsOptimized(8, 3) << endl;  // 6
    cout << countSolutionsOptimized(5, 2) << endl;  // 3
    cout << countSolutionsOptimized(3, 4) << endl;  // 2
    return 0;
}

Độ phức tạp

k = số nghiệm modulo p (thường rất nhỏ, ≤ 2^ω(p) với ω(p) số ước nguyên tố).