Số dự án Euler 338

Question

Tôi bị kẹt trên Project Euler problem 338. Đây là những gì tôi đã làm cho đến nay ...

Hãy biểu thị hình chữ nhật có chiều rộng và chiều cao x và y tương ứng (x,y). Để tạo thành các hình chữ nhật mới, bạn có thể xem xét việc cắt một loại cầu thang xuống đường chéo (như được trình bày trong phần mô tả vấn đề) với các bước d. Nhưng để tạo thành một hình chữ nhật mới, những thứ sau phải giữ: d|x và (d-1)|y hoặc (d+1)|y. Hình chữ nhật mới sau đó trở thành (x/d*(d-1), y/(d-1)*d) hoặc (x/d*(d+1), y/(d+1)*d). Rõ ràng khu vực hình chữ nhật mới giống như hình chữ nhật cũ.

Đó là đủ để khẳng định rằng G(10)=55 và G(1000)=971745 bằng vòng lặp qua tất cả có liên quan d và thêm tất cả các hình chữ nhật mới cho tập cẩn thận để đếm (x,y) và (y,x) chỉ một lần.

Vấn đề chính với phương pháp này là có thể tạo hình chữ nhật mới theo hai cách khác nhau. Ví dụ: (9,8) có thể chuyển thành cả hai (6,12) và (12,6) với d=3 và hoặc d-1 hoặc d+1 chia y. Hoặc một ví dụ khác về số (4,4) biến đổi thành cả hai (2,8) và (8,2) tương ứng với d=2 và d=1.

Tôi đã đủ may mắn để đọc this blog post. Nó loại bỏ sự cần thiết phải kiểm tra các bản sao bằng cách tìm kiếm một trong hai bên để thay thế.

def F(w, h): 
    if w&1 and h&1: return 0 
    if w<h: w,h = h,w 

    r = 0 
    x = 1 
    while x**2 <= w*h: 
     if (w*h)%x!=0 or x==h: 
      x += 1 
      continue 

     if w%(w-x)==0 or x%(x-h)==0: 
      r += 1 

     x += 1 

    return r 

def G(N): 
    s = 0 
    for w in range(1, N+1): 
     for h in range(1, w+1): 
      s += F(w,h) 

    return s 

G (10) sẽ đòi hỏi quá nhiều thời gian để giải quyết bất kể tốc độ F là mặc dù. Tôi nghĩ rằng cần phải sử dụng một số thuật toán sàng mà chúng tôi lặp qua tất cả x đếm số lượng (w, h) thỏa mãn h < = w < = 10 , x | (w * h) , x! = h và (wx) | w hoặc (xh) | x.

Tôi nghĩ rằng thuật toán O (n ^2/3) phải có thể ... nhưng tôi bị kẹt ở đây!

---

Sửa: Tôi không có quyền truy cập vào diễn đàn kể từ khi tôi không thể giải quyết nó. Đó là lý do tại sao tôi yêu cầu giúp đỡ. Tôi đã hoàn thành hầu hết các câu hỏi khác và muốn giải quyết câu hỏi này ngay bây giờ!

Chỉnh sửa 2: Tôi nghĩ rằng việc xem xét các khu vực bằng các yếu tố chính là kết thúc chết. Đó là bởi vì có 10 các khu vực khác nhau. Các hình chữ nhật có các vùng nguyên tố có 0 giải pháp, hình chữ nhật với các khu vực bán kết có 1 giải pháp nếu một trong số các số nguyên tố là 2 nếu không thì chúng có 0 giải pháp. Nhưng việc tính toán tất cả các giải pháp bán thời gian một mình sẽ mất quá nhiều thời gian vì chúng tôi cần đếm tất cả số nguyên tố p sao cho 2 * p không khả thi.

Sửa 3: Tôi đã rút gọn mã:

def G(N): 
    s = 0 
    for x in range(1, N): 
     for h in range(1, N+1): 
      if x==h: continue 
      for w in range(max(h, x**2//h), N+1): 
       if (w*h)%x==0 and x%(w-x)==0 and x%(x-h)==0: 
        s -= 1 

    for x in range(1, N): 
     for h in range(1, N+1): 
      if x==h: continue 
      for w in range(max(h, x**2//h), N+1): 
       if (w*h)%x==0 and w%(w-x)==0: 
        s += 1 

    for x in range(1, N): 
     for h in range(1, N+1): 
      if x==h: continue 
      for w in range(max(h, x**2//h), N+1): 
       if (w*h)%x==0 and h%(x-h)==0: 
        s += 1 

    return s 

Tôi không nghĩ phá vỡ mã brute-force xuống sẽ làm việc mặc dù. Hãy nhớ rằng chúng ta chỉ cần đếm các giải pháp (x, w, h) cho mỗi một trong ba vấn đề con này. Tổng cuối cùng như vậy sẽ có những hạn chế 0 < x < N, 0 < h < N + 1, x = h, tối đa (h, x/h) < w < N + 1, x |! Wh và xh | h.

Tôi nghĩ chúng ta nên bắt đầu với giả định rằng một số p thủ chia x, w, h hay thậm chí là x-h và sau đó xem những gì chúng ta có thể suy ra về các biến khác. Nếu điều đó hoạt động tốt, có thể xem xét p ^k cho tùy ý k.

Answer 1

Tôi không có một giải pháp, nhưng một cái gì đó thú vị cho Python. Tôi nhận ra rằng Python có thể được sử dụng như một công cụ thuận tiện cho việc ghi chú các thuật toán! Về cơ bản tôi đã viết xuống một chương trình tương tự như chương trình của bạn và bắt đầu chuyển đổi chương trình một cách hợp lý để lại kết quả không thay đổi. Tôi đã đưa ra

def order(x,y): 
    if x>=y: 
     return (x,y) 
    else: 
     return (y,x) 

N=1000 
num=set() 
for n in range(1, N+1): 
    for a in range(1,N//n+1): 
     for b in range(1,N//(n+1)+1): 
      if a==b: continue 
      num.add((order(a*n,b*(n+1)), order(b*n,a*(n+1)))) 

print(N, len(num)) 

Rõ ràng là bạo lực hoặc thậm chí một vòng lặp đơn giản trên 10^12 là không khả thi, nhưng có thể với thuật toán này, bạn có thể tìm thấy biểu thức đóng tại một số điểm. Nếu nó không phải là cho các ký tự thiết lập của num, nó sẽ là doable. Có lẽ người ta có thể tìm thấy điểm trùng lặp theo cách này.

Đây có thể là một ngõ cụt, nhưng nó vẫn còn khá mát mẻ mà Python có thể được sử dụng cho các ký hiệu và làm việc với các thuật toán :)

Bất kỳ sự tiến bộ về phía bạn?