10s là chết rồi bác, code chạy dưới 1s mà :v
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
2 Likes
Bài này k cần prime factors :V
4 Likes
Cái này nhìn có vẻ nhanh cơ mà đọc mãi mà không hiểu lắm.
Không biết bạn @rogp10 có thể implement bằng python để test thử được không nhỉ?
Kiểu như là reduce ước chung đến tận cùng luôn ấy bạn 
ABC
Mình chỉ dùng gcd thôi:
File.open "GOODSUBSET.INP" do |f|
n = f.gets
numbers = f.gets(chomp: true).split.map(:to_i)
end
numbers.sort!
h = Hash.new(0)
numbers.each do |num|
h.each do |k, v|
if num == k then h[k]=v+1; num=1; break; end
tmp = k.gcd(num)
if tmp != 1
if tmp == k then h[k] += 1
else h.delete(k); h[tmp] = v+1; h[k/tmp] = v; end
while num % tmp == 0 do num/= tmp; end; break if num == 1
end
end
h[num] = 1 if num != 1
end
File.write "GOODSUBSET.OUT", h.values.max
[3 5 15]: h = {3: 2, 5: 2}
[6 10 15 42]:
h[0] = {6: 1}
h[1] = {2: 2, 3: 1, 5: 1}
h[2] = {2: 2, 3: 2, 5: 2}
h[3] = {2: 3, 3: 3, 5: 2, 7: 1}
5 Likes
Sau n tiếng cố gắng porting qua python thì cũng xong, cơ mà code xấu quá nên hổng dám share ẩn dưới đây nhé.
Code xấu nên ẩn
N = 1000
MAX_N = 10**18
s = [random.randint(1, MAX_N) for _ in range(N)]
def f(d, num):
h = dict(d.items())
for k,v in d.items():
tmp = math.gcd(num, k)
if tmp != 1:
h.pop(k)
h[tmp] = h.get(tmp, 0) + v + 1
while k % tmp == 0: k = k // tmp
if k != 1: h[k] = v
while num % tmp == 0: num = num // tmp
if num != 1: h[num] = 1
return h
print("Result =", max(functools.reduce(f, s, {}).values()))
Code của @rogp10 bên python chạy dưới 0.5s.
Quá hịn luôn!
3 Likes
h[k/tmp] = v+1
h[k] = v+1 còn h[k/tmp] = v thôi chứ nhỉ :V
ví dụ 18 50 81
h[0] = {18:1}
h[1] = {2: 2, 9: 2, 25: 1} \leftarrow 9: 1 mới đúng chứ :V
h[2] = {2: 2, 9: 3, 25: 1} \leftarrow ra max = 3 là sai :V
cách này nhanh hơn vì nó ko cần phân tích hết thừa số nt 
Số lượng phần tử trong h tối đa = tất cả các ước ~ 15n, lặp 2 vòng numbers và h là O(n^2) :V mỗi lần lặp tìm gcd là tốn O(\log{m}), cộng thêm update h có thể tốn O(\log{n}) nữa (vì các key trong h được sắp xếp :V), vậy tổng cộng là O(n^2 \log{(nm)}) lẹ hơn dữ vậy :V :V :V à quên sort n nữa nhưng O cuối cùng cũng coi như có tính vào =]
à còn khó ở chỗ h đang loop mà đi xóa/thêm key thế kia làm sao nó cho phép :V :V
3 Likes
Như vậy chỉ còn cách h.keys.each thôi, duyệt trên mảng key.
2 Likes
hay tạo mảng to_delete với to_insert =] del với ins sau khi loop cũng được, vì h đã duyệt qua k rồi xóa sau cũng ko sao, k/tmp là coprime với num/(tmp^i) nên ko xét cũng ko sao, thêm vào sau khi duyệt cũng được
2 Likes
Ruby còn chậm hơn xD (seed 1: 1.0 - 1.2s, seed 2: 0.7 - 0.9s)
2 Likes
có vài case sai nha :V chắc thêm if else gì nhiều lắm :V Hoặc phải lưu tất cả phần tử chia hết cho k trong h :V
ví dụ 6 6 12 nó ra 2: 1, 6: 3 thừa số 2, khi thêm 1 số bội của 2 ví dụ 14 thì nó sẽ ra kết quả sai 2: 2, 6: 3, 7: 1, rồi thêm ví dụ 81 nó tách 6 thành 2: 3 và 3: 4 cộng vào sẽ ra 2: 5, kết quả cuối cùng ra 5 là sai vì 6 6 12 14 81 chỉ có 4 số chẵn đâu ra 5 số chẵn :V
h[k/tmp] thì k phải chia hết cho tất cả tmp, code của Stanley có làm điều này (nhưng lại ko duyệt h theo sorted keys :V). Vì k/tmp có thể = k (k = tmp^2), mà gán h[k] = v + 1 khác gán h[k/tmp] = v dẫn tới code ko đúng :V ví dụ 72 100 126 --> 100 tách 72 thành 4 và 18, ra kết quả 4: 2, 18: 1, 25: 1, gặp tiếp 126 nó tách 4 thành 2 và 2 :V h[k] gán 2: 3 đúng, nhưng h[k/tmp] gán 2: 2 là sai :V
chia k cho tmp tới khi ko chia được nữa (tạm viết là k///tmp) vẫn chưa đủ :V số dư còn lại có thể ghi đè lên kết quả: 126 chia cho 2 còn 63, tách tiếp 18 thành k=9 và k///tmp=2, khi gán h[k///tmp] = 1 là gán h[2] = 1 xóa sổ hết mấy kết quả lưu được của số 2 trước đó (ở đây là 2: 3) :V Cộng dồn cũng ko được vì nếu cộng dồn nó thành 2: 4, trong khi input chỉ có 3 số 72 100 126 :V Nếu lưu theo kiểu h[2] = {72,100,126} thì khi cộng thêm h[k///tmp] = {72} khi tách h[18] ra sẽ loại được trường hợp này, nhưng đpt sẽ thành O(n^3...) :V :V
2 Likes
Bài này nếu đếm ước thì sao nhỉ ?? Đếm ước của toàn bộ phần tử trong mảng, rồi trả về max là được
Đếm ước thì cũng phải phân tích thôi mà số lớn lắm.
3 Likes
Em mới nhìn lại input thì đúng là không chơi cách này được @@
Cách này muốn ổn thì phải có gcd(k, k') = 1\ \forall k, k' \in Keys(h), k \neq k' ở mọi thời điểm.
Xét [72 100 126]:
- gcd(100, 72) = 4
- gcd(72/4, 4) = 2 => xóa h[72] thay bằng h[2] = 1+1 = 2
- 18/2 = 9
- gcd(9, 4) = 1 => h[9] = 1 do từ số 18
- gcd(100/4, 4) = 1 => giữ số 25
- gcd(72/4, 4) = 2 => xóa h[72] thay bằng h[2] = 1+1 = 2
- h[25] = 1
- gcd(126, 2) = 2 => h[2] = 2+1 = 3
- gcd(63, 9) = 9 => h[9] = 2
- h[63/9] = 1
h = {2: 3, 7: 1, 9: 2, 25: 1}
vậy còn 18 với 63 nó tách 18 thành 9 và 2 thì sao :V Update h[2] như thế nào :V
à ờm 18 sẽ bị gcd(18,4)=2 nó loại rồi. Vậy cũng gần như phân tích thừa số nt rồi =]
chủ thớt đáp án đâu 
2 Likes
Với m = gcd(num, key)
thì num' = num/m và key' = key/m.
Nếu m \mid key' thì xóa h_{key'} thay bằng h_{m // key'} và h_m
Đặt m' = gcd(key', m) nếu m' \neq 1 ta xóa h_{key} thay bằng h_{m'} và h_{key'/m'}.
Đặt n' = gcd(num', m)\ (m' = 1), cho num'' = num/n' qua key tiếp theo, xóa h_{key} thay bằng h_{n'} và h_{key'}.
Áp dụng quy nạp có lẽ là OK
3 Likes
thay chữ num bằng num’ đi :V toán học làm gì có đổi giá trị cho biến :V
2 Likes
Tóm lại là nếu gcd bằng 1 là qua key mới, ngược lại thì phải test lại cả num và key cho gcd mới, mà chỉ có 1 trong 2 gcd có thể khác 1 (nếu ko thì không thể gọi là Greatest được).
2 Likes
chỉ cần tìm thêm 1 nấc m’ n’ nữa là đủ rồi, có thể cần thêm m’’ n’’ m’’’ … gì ko? :V :V
khi thêm num leftover sau khi đã lướt qua hết các keys trong h rồi có lẽ phải ktra lại xem các keys trong h ko chia hết cho num nữa mới thêm h[num] = 1 được?
ví dụ 6 12 thì đâu cần phân tích ra 2: 2, 3: 2 làm gì, 6: 2 là đủ. Nhưng m = 6 thì n=12 / 6 = 2, bước thêm h[num] = 1 cuối cùng có thể thêm h[2] = 1 vào dư thành 6: 2, 2: 1 :V
2 Likes
À vậy là bị lọt trường hợp chia hết rồi 
6 \div 6 = 1, 12 \div 6 = 2
trường hợp num' \mid gcd
6 \div 2 = 3 => h_6 \rightarrow h_2 := 2 (1 thì không được rồi)
Số 3 đi tiếp h_3 = 1
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?