Proyek Euler Nomor 338

Saya terjebak pada masalah 338 Proyek Euler. Inilah yang telah saya lakukan sejauh ini...

Mari kita nyatakan sebuah persegi panjang dengan lebar dan tinggi masing-masing x dan y (x,y). Untuk membentuk persegi panjang baru, Anda dapat mempertimbangkan untuk memotong semacam tangga menuruni diagonal (seperti yang ditunjukkan pada uraian masalah) dengan langkah d. Namun untuk membentuk persegi panjang baru, yang berikut ini harus memuat: d|x dan (d-1)|y atau (d+1)|y. Persegi panjang baru kemudian menjadi (x/d*(d-1), y/(d-1)*d) atau (x/d*(d+1), y/(d+1)*d). Tentunya luas persegi panjang yang baru sama dengan luas persegi panjang yang lama.

Itu sudah cukup untuk mengonfirmasi bahwa G(10)=55 dan G(1000)=971745 dengan mengulang semua d yang relevan dan menambahkan semua persegi panjang baru ke suatu himpunan, berhati-hatilah untuk menghitung (x,y) dan (y,x) hanya sekali.

Masalah utama dengan metode ini adalah membuat persegi panjang baru dapat dilakukan dengan dua cara berbeda. Misalnya, (9,8) dapat berubah menjadi (6,12) dan (12,6) dengan d=3 dan d-1 atau d+1 membagi y. Atau contoh lain dari (4,4) berubah menjadi (2,8) dan (8,2) dengan d=2 dan d=1 masing-masing.

Saya kemudian cukup beruntung membaca postingan blog ini. Ini menghilangkan kebutuhan untuk memeriksa duplikat dengan mencari salah satu sisinya.

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¹²) akan membutuhkan waktu yang terlalu lama untuk diselesaikan, tidak peduli seberapa cepat Fnya. Menurut saya, kita perlu menggunakan algoritma pengayakan yang mana kita mengulang semua x ‹ 10¹² menghitung berapa banyak (w,h) yang memenuhi h ‹= w ‹= 10^{12, x|(w*h), x != h dan (w-x)|w atau (x-h)|x.}

Saya pikir algoritma O(n^2/3) harus dimungkinkan... tapi saya terjebak di sini!

Sunting: Saya tidak memiliki akses ke forum karena saya tidak dapat menyelesaikannya. Itu sebabnya saya meminta bantuan. Saya telah menyelesaikan sebagian besar pertanyaan lainnya dan ingin menjawab pertanyaan ini sekarang!

Sunting 2: Menurut saya, mempertimbangkan luas berdasarkan faktor prima adalah jalan buntu. Hal ini karena terdapat 10²⁴ area yang berbeda. Persegi panjang dengan luas prima mempunyai 0 solusi, persegi panjang dengan luas semiprima mempunyai 1 solusi jika salah satu bilangan primanya adalah 2, jika tidak maka persegi panjang tersebut mempunyai 0 solusi. Namun menghitung semua solusi semiprima saja akan memakan waktu terlalu lama karena kita harus menghitung semua bilangan prima p sedemikian rupa sehingga 2*p ‹ 10²⁴ dan hal ini tidak mungkin dilakukan.

Edit 3: Saya telah menghapus kodenya:

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

Saya rasa memecahkan kode brute force tidak akan berhasil. Ingat, kita cukup menghitung solusi (x, w, h) untuk masing-masing submasalah tersebut. Penjumlahan terakhir akan mempunyai batasan 0 ‹ x ‹ N, 0 ‹ h ‹ N+1, x!=h, max(h, x²/h) ‹ w ‹ N+1, x|wh dan x-h|h.

Saya pikir kita harus mulai dengan asumsi bahwa suatu bilangan prima p membagi x, w, h atau bahkan x-h dan kemudian melihat apa yang dapat kita simpulkan tentang variabel lainnya. Jika itu berhasil, mungkin pertimbangkan p^k untuk k yang sewenang-wenang.