Tóm tắt đề bài

Cho số tự nhiên \(k\) (\(k \leq 100\)). Tìm số nguyên dương \(n\) nhỏ nhất sao cho trong tập hợp các ước số của \(n\) (không tính số 1) có ít nhất một đoạn gồm \(k\) số nguyên liên tiếp. Kết quả cần được chia dư cho \(10^9+7\).

Ví dụ: Với \(k=2\), số nhỏ nhất là \(n=6\) vì các ước của 6 (không kể 1) là \(\{2, 3, 6\}\), chứa đoạn liên tiếp \(\{2, 3\}\) có độ dài 2.

Phân tích

• Giả sử đoạn \(k\) số liên tiếp trong tập ước của \(n\) là \(\{x, x+1, x+2, \dots, x+k-1\}\).
• Theo định nghĩa ước số, \(n\) phải chia hết cho tất cả các số trong đoạn này. Tức là:
  
  \[ n \equiv 0 \pmod{i} \quad \forall i \in \{x, x+1, \dots, x+k-1\} \]
• Điều này tương đương với việc \(n\) phải là bội chung nhỏ nhất (BCNN) của các số trong đoạn đó:
  
  \[ n \geq \text{BCNN}(x, x+1, \dots, x+k-1) \]
• Để \(n\) nhỏ nhất, ta cần tìm giá trị \(x \geq 2\) sao cho \(\text{BCNN}(x, x+1, \dots, x+k-1)\) đạt giá trị nhỏ nhất.
• Một nhận xét quan trọng: BCNN của một dãy \(k\) số liên tiếp thường nhỏ nhất khi các số trong dãy đó nhỏ nhất. Cụ thể, trong bài toán này, đoạn liên tiếp bắt đầu từ \(x=2\) là \(\{2, 3, \dots, k+1\}\) sẽ cho BCNN nhỏ nhất.
  • Tại sao? Vì khi các số tăng lên, khả năng xuất hiện các số nguyên tố lớn hoặc các lũy thừa của số nguyên tố lớn hơn sẽ tăng, làm giá trị BCNN tăng rất nhanh. Với \(k \leq 100\), việc kiểm tra đoạn bắt đầu từ \(x=2\) là tối ưu nhất.

Hướng giải quyết

Thuật toán

1. Mục tiêu: Tính \(n = \text{BCNN}(2, 3, 4, \dots, k+1)\).
2. Sàng lọc số nguyên tố: Sử dụng sàng Eratosthenes để tìm các số nguyên tố và hỗ trợ phân tích thừa số nguyên tố nhanh cho các số từ \(2\) đến \(k+1\).
3. Tính BCNN:
   • Duy trì một mảng a[p] lưu trữ số mũ lớn nhất của số nguyên tố \(p\) xuất hiện trong phân tích thừa số nguyên tố của bất kỳ số nào từ \(2\) đến \(k+1\).
   • Với mỗi số \(i\) từ \(2\) đến \(k+1\):
     • Phân tích \(i = p_1^{e_1} \cdot p_2^{e_2} \dots\)
     • Cập nhật a[p_j] = max(a[p_j], e_j).
4. Tính kết quả:
   • \(n = \prod p_j^{a[p_j]} \pmod{10^9+7}\).
   • Lưu ý: Vì cần tính kết quả theo modulo, ta thực hiện nhân dồn và lấy dư ở từng bước.

Ví dụ minh họa (\(k=5\))

• Cần tìm BCNN của \(\{2, 3, 4, 5, 6\}\).
• Phân tích:
  • \(2 = 2^1\)
  • \(3 = 3^1\)
  • \(4 = 2^2\)
  • \(5 = 5^1\)
  • \(6 = 2^1 \cdot 3^1\)
• Số mũ lớn nhất: \(2^2, 3^1, 5^1\).
• \(n = 2^2 \cdot 3^1 \cdot 5^1 = 4 \cdot 3 \cdot 5 = 60\).

Độ phức tạp

• Thời gian: \(O(k \log k)\) để phân tích thừa số nguyên tố và tính BCNN. Với \(k=100\), thuật toán chạy cực nhanh.
• Bộ nhớ: \(O(k)\) để lưu trữ mảng đánh dấu và số mũ.

Code tham khảo

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

typedef long long ll;
const int N = 1005;
const int MOD = 1e9 + 7;

int p[N]; // p[i] lưu ước nguyên tố nhỏ nhất của i
int max_exp[N]; // max_exp[p] lưu số mũ lớn nhất của số nguyên tố p

// Hàm tính (a^b) % MOD
ll power(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    while (b > 0) {
        if (b % 2 == 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b /= 2;
    }
    return res;
}

// Sàng Eratosthenes để phân tích thừa số nguyên tố nhanh
void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (p[i] == 0) {
            for (int j = i; j <= n; j += i) {
                if (p[j] == 0) p[j] = i;
            }
        }
    }
}

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

    int k;
    if (!(cin >> k)) return 0;

    // Để có k số liên tiếp là ước, số nhỏ nhất là BCNN(2, 3, ..., k+1)
    int limit = k + 1;
    sieve(limit);

    // Phân tích từng số từ 2 đến k+1 để tìm số mũ lớn nhất của mỗi số nguyên tố
    for (int i = 2; i <= limit; i++) {
        int temp = i;
        while (temp > 1) {
            int prime = p[temp];
            int count = 0;
            while (temp % prime == 0) {
                count++;
                temp /= prime;
            }
            max_exp[prime] = max(max_exp[prime], count);
        }
    }

    // Tính BCNN bằng cách nhân các p^max_exp[p]
    ll ans = 1;
    for (int i = 2; i <= limit; i++) {
        if (max_exp[i] > 0) {
            ans = (ans * power(i, max_exp[i])) % MOD;
        }
    }

    cout << ans << endl;

    return 0;
}

Đáp án bài này chính là \(LCM(2->k+1).\)

Tuy nhiên, không phải là bạn lấy \(2 * 3*4*...*(k+1)\) (nhiều bạn hiểu nhầm là vì do \(GCD(2->k+1)=1\) nên các bạn suy thẳng ra điều kia), mà là các bạn phân tích từng số \(i\) ra thừa số nguyên tố, đếm phân phối, sau đó sẽ chạy qua mảng đó tìm kết quả.