Xác định tất cả các cách phân tích N thành tổng của 4 số nguyên tố

#22
  1. Sàng nguyên tố cho vào mảng A (m phần tử)
  2. F[i][j][k] là số cách phân tích tổng bằng i dùng k số nguyên tố thứ j
  3. F[i][j][k]= sigma( f[i-k*a[j]] [j-1] [0->4])
  4. in ra thì truy vết ngược :slight_smile:

Mới nghĩ thế test xem sao
:stuck_out_tongue: chắc là O(nm)

1 Like
#23

quy hoạch động hả a?

#24

á sorry đọc nhầm đề =)) bài này có vẻ đơn giản hơn :smiley: hiểu nhầm thành 1 số ko đc dùng quá 4 lần

#25

giờ đau đầu quá, chả nghĩ được gì… :cold_sweat:
để hôm nào hứng thú thì luyện thuật toán sau vậy :smiley:

ôi giời… :joy:

#26

Đêm khuya đầu óc có vấn đề :v:

  1. Sàng nguyên tố cho vào mảng A (m phần tử)
  2. F[i][j][k] là số cách phân tích tổng bằng i dùng k số nguyên tố từ 1->j :smiley: k=0…4
  3. F[i][j][k]= sigma( f[i-a[j]*t ] [j-1] [k-t])
  4. in ra thì truy vết ngược :slight_smile:
#27

ở đây t là gì vậy ạ?

#28

O(n2 logn) thì có lẽ là hơi lạc quan quá đó :joy:

phức tạp ở chỗ mỗi tổng thì có thể có nhiều cặp, ví dụ ở đây là k cặp có cùng tổng S, phải ghép k1 cặp có tổng S1 với k2 cặp có tổng S2 sao cho S1+S2=n, vậy thì độ phức tạp trong việc ghép 2 cặp lại với nhau ở đây là O(k1*k2) ~ O(k2)

có ~m2 cặp (m là số số ng tố nhỏ hơn n, ở đây tạm cho là m~n/logn)
tổng 1 cặp ko lớn hơn 2n. (vì tổng 2 số bé hơn n đương nhiên là bé hơn 2n).
như vậy mỗi tổng có khoảng m2 / n cặp, tức là k ~ m2 / n.

ghép 2 cặp có tổng (S1,S2) với nhau có thể tốn tới k2 ~ m4 / n2

dễ dàng chứng minh là S1 <= S2, như vậy cần ghép ~ n/2 lần 2 cặp.

tổng cộng là O(n * m4 / n2) ~ O(m4/n) ~ O(n3 / log4(n)). Hơi lớn nhưng O(n2logn) thì ít quá ko đúng big-O :joy:, dù sao thì cũng nhanh hơn duyệt trâu O(m4) n lần.

2 Likes
#29

t là số lượng số a[j] dùng để tạo tổng i :slight_smile:
t = 0->k

1 Like
#30

[email protected] ! :3

#31

Đúng rồi !!! ~~ Gony hiểu sai ý của tôi rồi …

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?