Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên dương i ≤ N sao cho gcd(i, N) = 1. Đây chính là bài toán tính hàm Euler totient φ(N). Hàm φ(N) là số nguyên dương nhỏ hơn hoặc bằng N và nguyên tố cùng nhau với N. Với N ≤ 10^9 và T ≤ 10, ta cần một thuật toán đủ nhanh để phân tích N và tính φ(N).

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

Cách Sử dụng công thức tính Euler totient

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

ll phi(ll n) {
    ll r = n;
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            r -= r / i;
        }
    }
    if (n > 1) r -= r / n;
    return r;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        cout << phi(n) << endl;
    }
    return 0;
}

• Time Complexity: O(√N) mỗi test case
• Space Complexity: O(1)

Thuật toán sử dụng công thức tính Euler totient: φ(N) = N * Π (1 - 1/p) với p là các thừa số nguyên tố của N. Đầu tiên, khởi tạo result = N. Duyệt qua các số i từ 2 đến √N. Nếu i là ước của N, ta chia hết N cho i cho đến khi không còn chia hết, sau đó cập nhật result = result - result/i. Nếu sau vòng lặp N > 1, thì N là một số nguyên tố và ta cập nhật tương tự. Độ phức tạp là O(√N) do duyệt đến căn bậc hai của N.

Cách Tối ưu hóa với số lớn nhất

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int ans = n;
        int m = n;
        for(int i = 2; i * i <= m; i++) {
            if(n % i == 0) {
                while(n % i == 0) {
                    n /= i;
                }
                ans = ans / i * (i - 1);
            }
        }
        if(n > 1) ans = ans / n * (n - 1);
        cout << ans << '\n';
    }
    return 0;
}

• Time Complexity: O(√N) mỗi test case
• Space Complexity: O(1)

Cách tiếp cận này tương tự như cách 1 nhưng có một chút thay đổi trong cách tính toán: ans = ans / i * (i - 1) thay vì result = result - result/i. Cả hai cách này đều tương đương mathematically. Biến m được dùng để lưu giá trị ban đầu của n cho vòng lặp, nhưng thực tế không cần thiết vì n được dùng để kiểm tra ước. Tuy nhiên, code này vẫn đảm bảo đúng logic. Đây là cách tính chuẩn của hàm Euler totient.

Cách Phiên bản với vector lưu ước số

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

long long 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() {
    int T;
    cin >> T;
    while (T--) {
        long long N;
        cin >> N;
        cout << phi(N) << endl;
    }
    return 0;
}

• Time Complexity: O(√N) mỗi test case
• Space Complexity: O(1)

Đây là phiên bản chi tiết hơn, giải thích rõ ràng từng bước. Thuật toán phân tích N thành các thừa số nguyên tố bằng cách duyệt từ 2 đến √N. Với mỗi thừa số p tìm được, ta chia hết N cho p và cập nhật result. Cuối cùng, nếu N còn lại > 1, thì N đó là số nguyên tố và cũng là thừa số của N ban đầu. Cách này giống hoàn toàn với cách 1 về logic và độ phức tạp.

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

Bài học kinh nghiệm

• Bài toán đếm số nguyên dương i ≤ N sao cho gcd(i, N) = 1 chính là bài toán tính hàm Euler totient φ(N).
• Công thức tính φ(N) = N * Π (1 - 1/p) với p là các thừa số nguyên tố phân biệt của N có thể được tính hiệu quả bằng cách duyệt các ước số.
• Với N ≤ 10^9, độ phức tạp O(√N) cho mỗi test case là hoàn toàn chấp nhận được (với T=10, tổng số phép toán khoảng 10√10^9 ≈ 310^5).

Lỗi thường gặp

• Sử dụng biến sai kiểu (vd: int thay vì long long) có thể gây tràn số vì N có thể lên tới 10^9.
• Quên kiểm tra trường hợp N > 1 sau vòng lặp, dẫn đến kết quả sai nếu N ban đầu có thừa số nguyên tố lớn hơn √N.
• Logic cập nhật sai (vd: result = result - result/p thay vì result = result - result/i) nhưng trong code mẫu đều đúng.