Hiểu bài toán

Bài toán yêu cầu tìm số nguyên dương lớn nhất D sao cho:

1. D là một số chính phương (perfect square).
2. D có thể được phân tích thành tích các số nguyên dương phân biệt, mỗi số không vượt quá N.

Nói cách khác, D phải là số chính phương và là bội số của tất cả các số từ 1 đến N (tức là bội chung nhỏ nhất của các số từ 1 đến N). Tuy nhiên, điều kiện 'phân tích thành tích' là quan trọng: nếu ta có thể chọn các thừa số phân biệt ≤ N để tích bằng D, thì D phải chia hết cho Bội chung nhỏ nhất (LCM) của các số từ 1 đến N, và các thừa số phân tích D phải là một tập con của {1, 2, ..., N}. D là số chính phương lớn nhất thỏa mãn điều này.

Thực chất, D chính là số chính phương lớn nhất là bội của LCM(1, 2, ..., N). Vì LCM(1, ..., N) là tích của các số nguyên tố mũ cao nhất ≤ N. Để D là số chính phương, mỗi thừa số nguyên tố trong LCM phải có số mũ chẵn. D là số chính phương lớn nhất chia hết cho LCM chính là LCM(1, ..., N) nhân với các thừa số nguyên tố cần thiết để tất cả các số mũ đều chẵn.

Ví dụ: N=4. LCM(1,2,3,4) = 12 = 2^2 * 3^1. Để thành số chính phương, cần nhân thêm 3 (2^2 * 3^2 = 36). D = 36.

Đầu vào có nhiều test case, N ≤ 10^7. Kết quả cần in ra D mod 10^9+7.

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

Cách Brute Force (Tìm Bội Chung Nhỏ Nhất - LCM)

#include <iostream>
#include <cmath>

using namespace std;

const long long MOD = 1e9 + 7;

// Hàm tính LCM của hai số
long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd(a, b)) * b;
}

void solve() {
    int n;
    while (cin >> n && n != 0) {
        long long l = 1;
        for (int i = 2; i <= n; i++) {
            l = lcm(l, i);
            // Kiểm tra tràn số sẽ rất phức tạp và chậm
        }
        // Tìm D là số chính phương lớn nhất chia hết cho l
        // Cách này chỉ hiệu quả cho N rất nhỏ, không khả thi với N=10^7
        cout << 0 << endl; 
    }
}

• Time Complexity: O(N^2 log N) - Quá chậm, không xử lý được N=10^7
• Space Complexity: O(1)

Cách này tính trực tiếp LCM của tất cả các số từ 1 đến N. Tuy nhiên, giá trị LCM tăng rất nhanh, ngay cả với N nhỏ (ví dụ N=20, LCM đã rất lớn). Việc tính toán trực tiếp và kiểm tra các bội số là không khả thi về thời gian và bộ nhớ.

Cách Sử dụng Prime Sieve và Phân tích thừa số nguyên tố

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

const int MAXN = 10000005;
const long long MOD = 1000000007;

int spf[MAXN]; // Smallest Prime Factor
vector<int> primes;

// Sieve of Eratosthenes để tìm ước nguyên tố nhỏ nhất
void sieve() {
    for (int i = 2; i < MAXN; i++) {
        if (spf[i] == 0) {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int j = 0; j < (int)primes.size() && primes[j] <= spf[i] && (long long)i * primes[j] < MAXN; j++) {
            spf[i * primes[j]] = primes[j];
        }
    }
}

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

void solve(int n) {
    long long D = 1;
    for (int p : primes) {
        if (p > n) break;

        // Tìm số mũ cao nhất của p không vượt quá n
        long long max_pow = p;
        while ((long long)max_pow * p <= n) {
            max_pow *= p;
        }

        // LCM(1..n) chứa p^max_pow
        // Để D là số chính phương, số mũ của p trong D phải là số chẵn.
        // Nếu max_pow là lẻ, ta cần nhân thêm p để nó thành chẵn (max_pow + 1).
        // Nếu max_pow là chẵn, ta giữ nguyên (max_pow).

        if (max_pow % 2 != 0) {
            max_pow++; // Làm cho số mũ chẵn
        }

        // Tính p^max_pow mod MOD và nhân vào D
        D = (D * power(p, max_pow)) % MOD;
    }
    cout << D << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sieve();
    int n;
    while (cin >> n && n != 0) {
        solve(n);
    }
    return 0;
}

• Time Complexity: O(MAXN log log MAXN) cho Sieve + O(N / log N) cho mỗi test case (vì số lượng prime ≤ N)
• Space Complexity: O(MAXN)

Phương pháp này dựa trên nhận định rằng D là số chính phương lớn nhất là bội của LCM(1..N). LCM(1..N) được tính bằng cách nhân các số nguyên tố p với số mũ là số nguyên lớn nhất e sao cho p^e ≤ N. Để D là số chính phương và chia hết cho LCM, số mũ của mỗi p trong D phải là số chẵn và ≥ e. Do đó, nếu e là số lẻ, số mũ của p trong D sẽ là e+1. Nếu e là số chẻ, số mũ là e.

Cách triển khai:

1. Sử dụng sàng nguyên tố (Sieve) để tìm các số nguyên tố và ước nguyên tố nhỏ nhất (SPF) hoặc chỉ lọc ra primes.
2. Với mỗi test case, duyệt qua các số nguyên tố p ≤ N.
3. Với mỗi p, tìm số mũ lớn nhất e sao cho p^e ≤ N.
4. Nếu e lẻ, nhân p^(e+1) vào D. Nếu e chẵn, nhân p^e vào D.
5. Tất cả các phép nhân đều thực hiện mod 10^9+7.

Độ phức tạp: Sieve ban đầu O(N log log N). Với mỗi test case, ta duyệt qua số lượng số nguyên tố ≤ N (khoảng N / ln N). Việc tìm số mũ e rất nhanh (logarithmic base p). Tổng thể nhanh chóng và xử lý được N=10^7.

Cách Tối ưu hóa (Nếu số lượng test case lớn)

// N/A (Logic tương tự Approach 2, nhưng có thể xử lý offline hoặc tối ưu bộ nhớ)

• Time Complexity: O(T * N / log N)
• Space Complexity: O(N)

Approach 2 về cơ bản đã là tối ưu. Nếu có quá nhiều test case và N đa dạng, có thể precompute kết quả cho mọi N ≤ 10^7, nhưng bộ nhớ có thể không cho phép (cần mảng 10^7 phần tử long long). Approach 2 xử lý từng test case là tốt nhất.

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

Bài học kinh nghiệm

• D là số chính phương lớn nhất chia hết cho LCM(1, 2, ..., N).
• LCM(1..N) = product(p^k), với p là số nguyên tố, k là số mũ lớn nhất để p^k ≤ N.
• Để D là số chính phương, số mũ của mỗi p trong D phải chẵn. Do đó, nếu k lẻ, ta cần nhân thêm p (tức là dùng p^(k+1)).

Lỗi thường gặp

• Làm tròn sai số mũ: Cần kiểm tra p^e ≤ N thay vì e = floor(log(N)/log(p)) do sai số số thực.
• Tràn số khi tính p^e: Cần kiểm tra điều kiện (long long)p * current_pow <= N thay vì tính trực tiếp p^e trước.
• Quên loại bỏ các số không phải nguyên tố khi duyệt.