Project Euler Number 338

Я застрял на проекте Эйлера задача 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

G(1012)) потребовалось бы слишком много времени для решения, независимо от того, насколько быстра F. Я думаю, что необходимо либо использовать какой-то алгоритм просеивания, где мы перебираем все x 12, считая, сколько (w,h) удовлетворяет h 12, x|(w*h), x != h и (w-x)|w или (x-h)|x.

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

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

Редактируйте 2 : Я думаю, что рассмотрение областей по основным факторам - это тупик. Это потому, что есть 1024 различных областей. Прямоугольники с простейшими областями имеют 0 решений, прямоугольники с полупремьерными областями имеют 1 решение, если один из праймов равен 2, иначе они имеют 0 решений. Но подсчет одних только растворов полупрайма занял бы слишком много времени, так как пришлось бы считать все примы p таким образом, что 2*p 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, а затем посмотреть, что мы можем вывести из других переменных. Если это сработает, то, возможно, рассмотрим pk для произвольного k.