Phân tích: Expensive Dinner

Bài toán này thoạt nhìn có vẻ khá đáng sợ:

• Có \(N!\) thứ tự mà những người bạn có thể đến.
• Không chỉ \(O(N!)\) quá chậm cho bài toán này, mà ngay cả \(O(N)\) cũng quá chậm!
• Tổng giá thực tế mà nhóm phải trả sẽ nhanh chóng vượt quá giới hạn của số nguyên 64 bit.

Khi ngay cả \(O(N)\) cũng quá chậm, bạn cần tạm quên việc lập trình và suy nghĩ. Ta phải tìm ra một nhận xét then chốt mới có thể bắt đầu.

Hãy cố định một thứ tự \((x_1,x_2,\ldots,x_N)\) của những người bạn. Gọi \(y_i\) là tổng giá của cả nhóm sau khi \(i\) người đầu tiên đã vào, người phục vụ đã được gọi nếu cần, và mọi người đều vui.

Quan sát 1

Giá trị này không phụ thuộc vào thứ tự mua đồ sau khi người phục vụ được gọi.

Theo định nghĩa, \(\operatorname{LCM}(x_1,x_2,\ldots,x_i)\) là số nhỏ nhất chia hết cho mọi \(x_1,x_2,\ldots,x_i\). Để tất cả mọi người đều vui, \(y_i\) phải chia hết cho các số ấy, nên \(y_i\ge \operatorname{LCM}(x_1,x_2,\ldots,x_i)\). Ngược lại, người bạn \(x_j\) sẽ không bao giờ mua một món khiến tổng giá vượt qua một bội của \(x_j\). Đặc biệt, không ai có thể mua một món khiến tổng giá vượt qua \(\operatorname{LCM}(x_1,x_2,\ldots,x_i)\). Vì \(y_{i-1}\le \operatorname{LCM}(x_1,x_2,\ldots,x_i)\), cuối cùng tổng giá sẽ đạt đúng giá trị này rồi dừng.

Gọi \(M\) là số lần người phục vụ được gọi. Khi đó, \(M\) bằng số chỉ số \(i\in\{1,2,\ldots,N\}\) sao cho \(y_i\ne y_{i-1}\). Ta quy ước \(y_0=0\), vì người bạn đầu tiên bước vào luôn gọi người phục vụ. Bài toán trở thành: làm thế nào để \(M\) lớn nhất, và làm thế nào để \(M\) nhỏ nhất?

Gọi \(p_1,p_2,\ldots,p_P\) là các số nguyên tố không vượt quá \(N\). Với mỗi \(i\), gọi \(e_i\) là số nguyên lớn nhất sao cho \(p_i^{e_i}\le N\).

Quan sát 2

Gọi \(P'=1+\sum_i e_i\), tức là số lũy thừa nguyên tố không vượt quá \(N\), kể cả số \(1\). Giá trị lớn nhất của \(M\) đúng bằng \(P'\).

Cho các bạn đến theo thứ tự \(1,2,\ldots,N\). Mỗi người có chỉ số là một lũy thừa nguyên tố sẽ làm tổng giá tăng, nên \(\max M\ge P'\).

Mặt khác, theo Quan sát 1, tổng giá luôn là một bội chung nhỏ nhất, và mỗi lần tăng thì nó tăng thành một bội của chính nó. Vì vậy, mỗi lần gọi người phục vụ, tổng các số mũ trong phân tích thừa số nguyên tố của tổng giá phải tăng. Sau khi người đầu tiên đến, tổng này ít nhất bằng \(0\); cuối cùng nó bằng \(P'-1\). Do đó, sau người đầu tiên, người phục vụ chỉ có thể được gọi nhiều nhất \(P'-1\) lần. Tính cả lần tăng ban đầu, \(M\le P'\).

Quan sát 3

Nếu \(N>1\), giá trị nhỏ nhất của \(M\) bằng \(P\).

Cho những người đến đầu tiên lần lượt có chỉ số \(p_1^{e_1},p_2^{e_2},\ldots,p_P^{e_P}\). Sau khi họ đến, tổng giá đã bằng

Vì thế, không người nào đến sau làm thay đổi tổng giá, và trong trường hợp này \(M=P\).

Theo chiều ngược lại, không có số nào không vượt quá \(N\) lại chia hết đồng thời cho hai số khác nhau \(p_i^{e_i}\) và \(p_j^{e_j}\). Hai số này nguyên tố cùng nhau và đều lớn hơn \(\sqrt N\): nếu một số không vượt quá \(\sqrt N\), ta còn có thể tăng số mũ của nó, trái với tính cực đại. Vì vậy, không một người bạn nào có thể khiến tổng giá đồng thời chia hết cho hai phần tử khác nhau trong \(\{p_1^{e_1},p_2^{e_2},\ldots,p_P^{e_P}\}\). Do đó, người phục vụ phải được gọi ít nhất \(P\) lần.

Với dữ liệu nhỏ, chỉ cần tính trực tiếp \(P\) và \(P'\) rồi lấy độ chênh lệch. Dữ liệu lớn cần thêm một mẹo. Có quá nhiều số nguyên tố nhỏ hơn \(10^{12}\) để đếm hết, nhưng tính \(P'-P\) lại dễ hơn nhiều.

Từ các định nghĩa, \(P'-P\) chính là số lượng số nguyên không vượt quá \(N\) có dạng \(p^e\) với \(e\ne1\). Khi \(e=0\), ta được số \(1\). Khi \(e>1\), \(p\le10^6\), nên có thể dễ dàng liệt kê mọi số nguyên tố cần thiết, chẳng hạn bằng Sàng Eratosthenes. Có thể xem lời giải của các thí sinh khác để tham khảo một cài đặt đầy đủ.

Nhận xét bổ sung

Sàng Eratosthenes chạy trong \(O(M\log\log M)\), nên cách cài đặt đơn giản nhất ở trên có tổng thời gian \(O(\sqrt N\cdot T\cdot\log\log N)\).

Ta còn có thể làm tốt hơn: tiền xử lý và sắp xếp mọi lũy thừa nguyên tố nhỏ hơn \(10^{12}\) có số mũ khác \(1\), rồi dùng tìm kiếm nhị phân để đếm rất nhanh bao nhiêu giá trị không vượt quá \(N\) cho từng bộ test. Điều này không cần thiết để giải bài, nhưng giảm thời gian xuống \(O(\sqrt N\log\log N+T\log N)\). Việc chứng minh cận thời gian này hơi tinh tế.

Dựa trên phân tích chính thức của Google Code Jam.