Hiểu bài toán

Cho hai số nguyên dương $a$ và $m$ ($1 \le a < m \le 10^{10}$). Yêu cầu đếm số lượng số nguyên dương $k$ trong khoảng $0 \le k < m$ sao cho $\gcd(a+k, m) = \gcd(a, m)$.

Các cách tiếp cận

Cách Brute Force (Tối ưu hóa)

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    long long a, m;
    cin >> a >> m;
    long long g = gcd(a, m);
    long long m_prime = m / g;

    long long count = 0;
    for (long long k = 0; k < m; ++k) {
        // Kiem tra dieu kien
    }
    return 0;
}

• Time Complexity: O(m)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất, thử tất cả các giá trị $k$ từ $0$ đến $m-1$. Tuy nhiên, với $m$ lên tới $10^{10}$, độ phức tạp $O(m)$ là không thể chấp nhận được và sẽ gây ra lỗi thời gian (Time Limit Exceeded). Phương pháp này chỉ mang tính chất tham khảo để hiểu đề bài.

Cách Sử dụng Euler Totient Function

#include <iostream>
#include <cmath>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

long long euler_phi(long long n) {
    long long result = n;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

int main() {
    long long a, m;
    cin >> a >> m;
    long long g = gcd(a, m);
    long long m_prime = m / g;
    cout << euler_phi(m_prime);
    return 0;
}

• Time Complexity: O(sqrt(m))
• Space Complexity: O(1)

Đặt $g = \gcd(a, m)$ và $m' = m/g$. Ta cần đếm số $k$ sao cho $\gcd(a+k, m) = g$. Điều này tương đương với việc tìm số $k$ sao cho $\gcd((a+k)/g, m') = 1$. Vì $a \equiv 0 \pmod g$ nên $a+k \equiv k \pmod g$. Để $g$ chia hết cho $a+k$, ta cần $k$ chia hết cho $g$. Gọi $k = x \cdot g$. Khi đó $0 \le x \cdot g < m \implies 0 \le x < m'$. Bài toán quy về đếm số $x$ trong khoảng $[0, m'-1]$ sao cho $\gcd(a/g + x, m') = 1$. Vì $\gcd(a/g, m') = 1$, số lượng $x$ thỏa mãn chính là $\phi(m')$, số totient Euler của $m'$. Hàm $\phi(n)$ có thể tính trong thời gian $O(\sqrt{n})$. Phương pháp này hiệu quả với $m \le 10^{10}$.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể biến đổi về dạng đếm số nguyên $x$ trong khoảng $[0, m'-1]$ sao cho $\gcd(x, m') = 1$ (hoặc tương đương), trong đó $m' = m / \gcd(a, m)$.
• Số lượng số nguyên dương không vượt quá $n$ và nguyên tố cùng nhau với $n$ được tính bằng hàm Euler Totient $\phi(n)$.
• Nếu $\gcd(a, m) = 1$, đáp án luôn là $m-1$ (trừ trường hợp đặc biệt $k=m$).

Lỗi thường gặp

• Sử dụng thuật toán Euclid mở rộng (Extended Euclidean Algorithm) thay vì tính $\gcd$ thông thường.
• Sai lệch trong việc biến đổi điều kiện $\gcd(a+k, m) = \gcd(a, m)$ sang dạng $\gcd(x, m') = 1$.
• Quên kiểm tra các trường hợp biên hoặc xử lý sai khi $a+k$ không chia hết cho $g$ (dù theo phân tích trên thì điều này không xảy ra nếu ta chọn $k$ đúng quy tắc).