Проект Эйлера № 338

Question

Я застрял на Project Euler проблема 338 . Вот что я сделал до сих пор ...

Обозначим прямоугольник с шириной и высотой x и y соответственно (x,y). Чтобы сформировать новые прямоугольники, вы можете порезать лестницу вниз по диагонали (как показано в описании проблемы) с помощью d шагов. Но чтобы сформировать новый прямоугольник, должно быть следующее: d|x и либо (d-1)|y, либо (d+1)|y. Новый прямоугольник становится либо (x/d*(d-1), y/(d-1)*d), либо (x/d*(d+1), y/(d+1)*d). Очевидно, что площадь новых прямоугольников такая же, как у старого прямоугольника.

Этого было достаточно, чтобы подтвердить G(10)=55 и G(1000)=971745, перебрав все соответствующие d и добавив все новые прямоугольники в набор, стараясь подсчитать (x,y) и (y,x) только один раз.

Основная проблема этого метода заключается в том, что можно создать новый прямоугольник двумя различными способами. Например, (9,8) может преобразовываться в (6,12) и (12,6) с d=3 и либо d-1 или d+1 с делением y. Или другой пример преобразования (4,4) в (2,8) и (8,2) с d=2 и d=1 соответственно.

Мне посчастливилось прочитать это сообщение в блоге . Это устраняет необходимость проверки на наличие дубликатов путем поиска одной из сторон.

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 ¹² ) потребует слишком много времени, чтобы решить независимо от того, как быстро F. Я думаю, что необходимо либо использовать какой-то алгоритм просеивания, где мы перебираем все x <10 <sup>12 , считая, сколько (w, h) удовлетворяет h <= w <= 10 <sup>12, x | (w * h), x! = h и (wx) | w или (xh) | x.

Я думаю, что алгоритм O (n ^2/3 ) должен быть возможен ... но я застрял здесь!

---

Редактировать : У меня нет доступа к форуму, так как я не могу его решить. Вот почему я прошу о помощи. Я выполнил большинство других вопросов и хочу заняться этим вопросом сейчас!

Редактировать 2 : Я думаю, что рассмотрение областей по основным факторам - это тупик. Это потому, что есть 10 ²⁴ разных областей. Прямоугольники с простыми областями имеют 0 решений, прямоугольники с полупростыми областями имеют 1 решение, если одно из простых чисел равно 2, в противном случае они имеют 0 решений. Но подсчет всех полупростых решений занял бы слишком много времени, так как нам нужно было бы сосчитать все простые числа p так, чтобы 2 * p <10 <sup>24 , что невозможно.

Редактировать 3 : Я сократил код:

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

Я не думаю, что взлом кода грубой силы будет работать, хотя. Помните, что достаточно просто подсчитать решения (x, w, h) для каждой из этих трех подзадач. Последнее такое суммирование будет иметь ограничения 0 2 / h)

Я думаю, что мы должны начать с предположения, что некоторое простое число p делит x, w, h или даже x-h, а затем посмотрим, что мы можем сделать о других переменных. Если это работает хорошо, возможно, рассмотрим p ^k для произвольного k.

Answer 1

У меня пока нет решения, но что-то интересное для Python.Я понял, что Python можно использовать как удобный инструмент для обозначения алгоритмов!По сути, я записал программу, похожую на вашу, и начал логически преобразовывать программу, оставляя результаты без изменений.Я придумал

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))

Очевидно, что грубая сила или даже простой цикл над 10 ^ 12 неосуществимы, но, возможно, с помощью этого алгоритма можно найти выражение закрытой формы в некоторой точке.Если бы не было установленного символа num, это было бы выполнимо.Может быть, таким путем можно найти повторяющиеся точки.

Это может быть тупик, но все же очень здорово, что Python можно использовать для нотации и работы с алгоритмами:)

Любой прогресс на вашемсторона