qui hoạch động thôi thím.
với mỗi số, phân tíhc nó thành thừa số nguyên tố.
vd n = 3, có 2, 6, 7
2 = 2
6 = 3 * 2
7 = 7
có thể biểu diễn mỗi số tạo được bằng một dãy số [b_0,b_1,b_2, ...] , vậy số đó là 2^b_0 * 3 ^b_1 * 5 ^ b_2 * ...
nhận thấy a <= 500, và lũy thừa lớn nhất của các snt <= 500 là: 2^8 <= 500, 3^5, 5^3 ,7^3, 11^2, 13^2, 17^2, 19^2. các snt > 19 thì chỉ có thể xuất hiện 0 hoặc 1 lần trong mỗi phân tích, thế nên ko cần lưu lại. vậy có tối đa 9 * 6 * 4 * 4 * 3 * 3 * 3 *3 = 69984 trạng thái trong mảng DP.
vậy với mỗi phân tích thừa số nguyên tố, loại bỏ các thừa số > 19, lúc này số này số LCM có thể tạo ra là 69984.
vậy mảng dp[70000], thể hiện tới vị trí i, đếm số luần mỗi LCM từ 1 -> 70000 xuất hiện. và tính LCM với a hiện tại và cộng vào. dp[LCM(j, a)] với mỗi j từ 1 tới 70000 và LCM(j, a) < 70000. với các a có thừa số > 19, số thừa số > 19 trong a chỉ có thể là 0 hoặc 1, lúc này tách riêng các a này ra tập khác. lấy riêng các thừa số > 19 ra. trong tập này, nhận thấy nếu có thừa số > 19 thì các thừa số còn lại tích không quá 21 (500 / 23 ~= 21). lúc này chỉ cần brute force qua tập này là xong O(2^21).