Ý tưởng

Đầu tiên, ta cần phân tích thừa số nguyên tố của tất cả các số từ \(l\) đến \(r\). Gọi \(v_p(x)\) là số mũ của \(p\) trong phân tích thừa số nguyên tố của \(x\). Ví dụ \(v_2(6) = 1, v_2(24) = 3\).

Gọi \(BCNN(l, l + 1, ..., r) = A\)

Khi đó \(v_p(A) = max(v_p(l), v_p(l + 1), ..., v_p(r))\). Tính \(v_p(A)\) cho tất cả các số nguyên tố \(p\) rồi nhân lại, ta được kết quả.

Subtask 1-4

Do \(r \leq 10^7\) nên chúng ta có thể sử dụng sàng nguyên tố để phân tích nhân tử.

Subtask 5

Nhận xét: mỗi số trong đoạn \([l, r]\) có tối đa một ước nguyên tố lớn hơn \(10^7\) vì \(l \leq r \leq 10^{14}\), và nếu có thì số mũ của ước đó trong phân tích TSNT là \(1\).

Với mỗi số nguyên tố \(p\) nhỏ hơn \(10^7\), ta sẽ tính \(v_p(l), v_p(l + 1), ..., v_p(r)\). Chúng ta chỉ cần quan tâm các số là bội của \(p\) nên có thể làm như sau:

for tất cả các bội x của p trong [l, r]:
   tính thừa số mũ của p trong x
   while (x % p == 0): x /= p

Sau khi hoàn thành đoạn code trên cho tất cả số nguyên tố \(p < 10^7\), các số trong đoạn \([l, r]\) sẽ trở thành \(1\) hoặc một số lớn hơn \(1\), và số lớn hơn \(1\) đó chính là ước nguyên tố duy nhất của nó lớn hơn \(10^7\).

Ví dụ số \(6(10^9+7)\) sau khi chia cho \(2\) và \(3\) sẽ còn lại \(10^9+7\).

Từ đó chúng ta có được phân tích thừa số nguyên tố của mỗi số trong đoạn \([l, r]\). Áp dụng vào công thức LCM, chúng ta có được đáp án. Một chi tiết nhỏ trong bài toán này là các số nguyên tố còn lại sau khi chia có thể lớn hơn \(10^9\) (có thể tầm \(10^{14}\)) nên các bạn cần lưu ý việc tràn số trong khi tính toán.

Độ phức tạp:

Đặt \(r - l = n\). Với mỗi số nguyên tố \(p\), số bội của \(p\) trong đoạn \([l, r]\) là khoảng \(\displaystyle \frac{n}{p}\). Nên tổng số phép toán là \(\displaystyle \frac{n}{2} + \frac{n}{3} + \frac{n}{5} + ... < n \times (1 + \frac{1}{2} + \frac{1}{3} + ...) =O(n\log{n})\).

Đó là lý do bài toán có điều kiện \(r - l \leq 10^6\).