Good Subset
Cho dãy n số nguyên dương, tìm tập con có số lượng phần tử lớn nhất sao cho GCD của tập này lớn hơn 1.
Dữ liệu: Vào từ file GOODSUBSET.INP:
- Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 1000)
- Dòng thứ hai chứa n số nguyên dương ai (2 ≤ n ≤ 10^18)
Kết quả: Ghi ra file GOODSUBSET.OUT một số nguyên duy nhất là số lượng phần tử của tập con lớn nhất thỏa mãn.
Ví dụ:
GOODSUBSET.INP GOODSUBSET.OUT 4
6 15 10 423
Ai có ý tưởng gì k ạ
Thuật toán “stupid” nhất bạn có thể nghĩ ra để giải bài toán này là gì? Hãy implement thuật toán đó trước khi nghĩ tới thuật toán tối ưu hơn đi bạn.
PS: với ví dụ trong đề: hãy đếm những số chia hết cho 2 hoặc 3 sẽ ra được kết quả
GCD lớn hơn 1, tức là ta phải nhóm ntn đó mới được => …
chỉ có 2 và 3 là số nguyên tố thôi sao
lỡ dãy đó là {2 3 6 10 5 25 125} thì sao?
“với ví dụ trong bài” mà 
Đã nói đến GCD là nhắc đến thừa số nguyên tố (theo đúng định nghĩa).
bài này dùng quy hoạch động, idea tương tự với một ví dụ quy hoạch động level vỡ lòng trong cuốn Giải thuật và lập trình - Lê Minh Hoàng
t[i] = max phần tử khi lấy a[i] vào set kết quả
đáp án là max(t[i])
với mỗi t[i] thì cost là n => total cost: O(n^2)
Bài này O(n^2) thì có vẻ đúng rồi.
Nhưng cách quy hoạch động kia của bạn hình như sai sai.
Khi xét t[i] việc lấy hay bỏ a[i] sẽ có ảnh hưởng tới kết quả, nên ở mỗi t[i] sẽ cần tách ra 2 trường hợp lấy/bỏ a[i] => quay về bài toán liệt kê tập con => là thành O(2^N) rồi á
ở đây không có option bỏ, chỉ có lấy và tìm xem nếu lấy thì kết quả tốt nhất sẽ như nào?, khi lấy a[i] thì tìm trong những kết quả trước đó xem a[i] nhét vô set nào thì tốt nhất
xem bài chuỗi con chung dài nhất để biết, và tất nhiên còn phải có thêm 1 mảng g song song với mảng t để ghi lại “thông tin” của những kết quả trước đó để check điều kiện lấy a[i] vào set kết quả đó thì sẽ có gcd là 1 hay không phải 1
và trong các kết quả tốt nhất (lượng phần tử trong set có a[i]) thì sẽ lại phải lấy kết quả có ước chung tốt nhất
bài này nâng cao hơn bài chuỗi dãy con chung nhưng idea tương tự
update
{2,3,5,30,3}
30 có thể match với cả 3 set trước đó (trở thành set mới có 2 phần tử), idea trên bị sai
cần phải tổ chức dữ liệu của mảng g lại sao cho phù hợp (có thể phải là mảng 2 chiều)
Nghĩ lại thì chia thử sẽ không 100% được vì quá lâu (10^9*1000), nhưng GCD thì cực nhanh nên ta xếp dãy không giảm (để đảm bảo các thành phần là nhỏ nhất) và làm một cấu trúc đánh dấu.
ko có lời giải luôn bó tay rồi 
Bài này có 2 input là n là số lượng phần tử và m là giá trị phần tử lớn nhất. Cách duyệt trâu là O(2^n), cách 2 trong g4g kia là O(nm), cách 3 trong g4g là O(tùm lum) mà thấy có space O(m) là tiêu rồi
cách của prog10 10^9*1000 chắc là phân tích thừa số nguyên tố của n phần tử ra, gộp các thừa số nguyên tố này lại thành 1 set, rồi với mỗi thừa số nt k, đếm số phần tửchia hết cho k trong mảng ban đầu, lấy thừa số nt nào có nhiều phần tử chia hết nhất thì số phần tử chia hết đó là đáp án. Cách này bước 1 phân tích thừa số nt n phần tử là O(n\sqrt{m}), bước 2 có tối đa 15n số nguyên tố khác nhau (vì 1 số < 10^{18} có tối đa 15 thừa số nt: 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot41\cdot43\cdot47 \approx 6.149\times10^{17}), duyệt tìm số phần tử chia hết cho mỗi thừa số nt tốn n lần vậy bước này tốn O(n^2), tổng kết O(n\sqrt{m} + n^2) vẫn ko kịp vì vướng cái bước phân tích thừa số nt :V lỡ 1000 số đều là số nt \approx 10^{18} thì chết :V
https://en.wikipedia.org/wiki/Pollard's_rho_algorithm có thuật toán phân tích thừa số nt lẹ hơn O(\sqrt{n}) :V edit: cũng là O(\sqrt{n}) nếu n là số nt thì phải :V
edit: bước 2 có thể giảm xuống O(n \log{n}) hoặc O(n) nhưng vẫn bị vướng bước 1 :V
Subsequence quá oải, nhưng mà subset thì ta xếp lại được và làm như sau:
Lập set count_divisibles[], trong đó count_divisibles[a[0]] = 1
Lặp qua key của count_divisibles, lấy gcd(k, a[i]), nếu gcd khác 1 và k thì xóa k và thêm cho a[i]/gcd và k/gcd, chia a[i] cho gcd vừa tìm được.
Worst case: 1000 số nguyên tố.
chắc xài Rabin-Miller để tìm số nt lẹ khi chạy Pollard-rho =]
RM 9 test ăn chặt (có thể khẳng định luôn) 
từ 20*9 đến 60*9 phép chia.
RM có hai trường hợp False:
RM tốn O(sb) trong đó s là số witness, b là số bit, ở đây 10^{18} chắc là 60 bit :V Theo link này:
https://miller-rabin.appspot.com/
thì deterministic RM chỉ cần 7 witness a \in \{2,325,9375,28178,450775,9780504,1795265022\} thay vì 12 witness như wikipedia :V Nhưng bước x \leftarrow a^d \mod{n} trong witness do n là số 64-bit nên cần xài __int128 :V Tuy chỉ cần khoảng 60 phép nhân và mod nhưng là nhân mod 128-bit number, chắc cũng lâu :V Nghe nói chạy ~1ms mỗi số, 1000 số ko biết có kịp ko :V
Cái này là Python mà.
ủa vậy à =] C++ chắc lẹ hơn 10 lần vậy ngon rồi =]
Ngoài ra số trong Python là immutable nữa, chứ ko lẽ 1 giây ko làm được 1 triệu phép chia sao?
1 phép chia 128-bit chắc bằng 16 phép chia 32-bit, 16 triệu phép chia chắc cũng xấp xỉ 1 0.1 giây 
N = 1000
MAX_N = 10**18
s = [random.randint(1, MAX_N) for _ in range(N)]
r = collections.Counter(itertools.chain(*map(sympy.primefactors, s))).most_common(1)[0]
print("Result =", r[1])
print("Most common factor =", r[0])
Random linh tinh mà với kiểu tính prime factors rồi count cũng chỉ cỡ dưới 10s vầy chắc là chốt được rồi ha =]]
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?