Với số tự nhiên A, tôi muốn tìm tất cả các cặp số tự nhiên (B, C) sao cho B * C * (C + 1) = A

Question

Cách nhanh nhất để làm điều đó là gì?

aproach đơn giản của tôi:

for (C = 1;C<sqrt(A);C++) { 
B=A/(C*(C+1)); 
if B is natural then add B,C to the list of possible pairs. 
} 

Nó có thể được thực hiện trong vòng chưa đầy O (sqrt (A))?

Giải pháp

Như Egor Skriptunoff câu trả lời, nó có thể được thực hiện một cách dễ dàng trong thời gian O (cube_root (A)).

Dưới đây là triển khai javascript đơn giản.

function findBCs(A) { 
    if (A/2 != Math.floor(A/2)) return []; 
    var solution = []; 
    var i; 
    var SR3 = Math.pow(A, 1/3); 
    for (i = 1; i <= SR3; i++) { 
     var B, C; 
     C = i; 
     B = A/(C * (C + 1)); 
     if (B == Math.floor(B)) { 
      solution.push([B, C]); 
     } 

     B = i; 
     C = (-1 + Math.sqrt(1 + 4 * A/B))/2; 
     if (C == Math.floor(C)) { 
      solution.push([B, C]); 
     } 
    } 

    return solution; 
} 

Tôi chấp nhận câu trả lời của Meh vì nó sẽ tốt hơn (ngoài việc triển khai phức tạp hơn một chút và tôi chưa thử nghiệm).

Answer 1

Bước 1: Yếu tố A

Bước 2: Tìm tập S của tất cả các ước từ thừa số nguyên tố của A.

Bước 3: Đối với mỗi ước c trong S, kiểm tra xem c + 1 chia Một quá. Nếu có thì b = A/(c * (c + 1)) là một giải pháp. (Điều này sử dụng c và c + 1 là coprime, do đó nếu cả c và c + 1 chia A thì c * (c + 1)). Sự phức tạp của điều này phụ thuộc vào phương pháp được sử dụng cho yếu tố AEg, nếu bạn thực hiện ví dụ Pollard-rho (tương đối đơn giản) thì sự phức tạp của việc thực hiện là về O (A^0,25) ở mức tồi tệ nhất trường hợp. Và điều này vẫn không phải là câu trả lời tốt nhất có thể. Có tất nhiên thuật toán bao thanh toán tốt hơn. Ngoài ra nếu đầu vào của bạn là một trường hợp đặc biệt với rất nhiều ước, sau đó bao thanh toán có thể dễ dàng và số lượng ước là vấn đề hạn chế.

Lợi thế của phương pháp này tất nhiên là bạn sẽ dành nhiều thời gian cho một chức năng hữu ích chung (tức là yếu tố), điều này sẽ đơn giản hóa việc giải quyết các vấn đề tương tự khác. Việc thực hiện của riêng tôi Pollard-rho trong Python cần tổng cộng 0,03 s cho 20 ví dụ với 15 chữ số được đăng bởi 6502, ít nhất là một sự tăng tốc của một yếu tố 1000. Các triển khai phức tạp hơn sẽ dẫn đến những cải tiến lớn hơn nhiều.

Để so sánh, triển khai Python nhanh chóng và dơ bẩn của phương pháp O (A^(1/3)) do Egor Skriptunoff đề xuất cần 0,7 cho cùng một danh sách. Điều này tất nhiên là một kết quả tốt cho một phương pháp dễ thực hiện.

Answer 2

Nó có thể được thực hiện trong O(cube_root(A))
Trên thực tế, một trong những con số của bạn B và C phải nhỏ hơn cube_root(A)

Answer 3

trăn này dường như làm việc:

from __future__ import division 
from math import sqrt 

def bcc1(a): 
    ans = [] 
    if a % 2: return ans # for odd a 
    for b in range(1, a // 2 + 1): 
     c = max(1, int(sqrt(a/b))) 
     if b*c*(c+1) == a: 
      ans.append((b,c)) 
    return ans 

for a in range(2, 51, 2): 
    print('a: %2i -> (b, c): %r' % (a, bcc1(a))) 

Sản lượng sản xuất là:

a: 2 -> (b, c): [(1, 1)] 
a: 4 -> (b, c): [(2, 1)] 
a: 6 -> (b, c): [(1, 2), (3, 1)] 
a: 8 -> (b, c): [(4, 1)] 
a: 10 -> (b, c): [(5, 1)] 
a: 12 -> (b, c): [(1, 3), (2, 2), (6, 1)] 
a: 14 -> (b, c): [(7, 1)] 
a: 16 -> (b, c): [(8, 1)] 
a: 18 -> (b, c): [(3, 2), (9, 1)] 
a: 20 -> (b, c): [(1, 4), (10, 1)] 
a: 22 -> (b, c): [(11, 1)] 
a: 24 -> (b, c): [(2, 3), (4, 2), (12, 1)] 
a: 26 -> (b, c): [(13, 1)] 
a: 28 -> (b, c): [(14, 1)] 
a: 30 -> (b, c): [(1, 5), (5, 2), (15, 1)] 
a: 32 -> (b, c): [(16, 1)] 
a: 34 -> (b, c): [(17, 1)] 
a: 36 -> (b, c): [(3, 3), (6, 2), (18, 1)] 
a: 38 -> (b, c): [(19, 1)] 
a: 40 -> (b, c): [(2, 4), (20, 1)] 
a: 42 -> (b, c): [(1, 6), (7, 2), (21, 1)] 
a: 44 -> (b, c): [(22, 1)] 
a: 46 -> (b, c): [(23, 1)] 
a: 48 -> (b, c): [(4, 3), (8, 2), (24, 1)] 
a: 50 -> (b, c): [(25, 1)]