프로젝트 오일러 번호 338

Question

프로젝트 오일러 problem 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으로 각각 변환합니다.

나는 운이 좋게도 this blog post을 읽을 수있었습니다. 대신에 측면 중 하나를 검색하여 중복 여부를 확인할 필요가 없습니다.

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 그래도 얼마나 빨리의 해결하기 위해 너무 오래 필요합니다. 나는 우리가 모든 것을 반복 할 때 어떤 종류의 체질 알고리즘을 사용할 필요가 있다고 생각한다. 얼마나 많은 (w, h)가 h를 만족하는지 계산한다. < = w < = 10 , x | (w * h) , x! = h 및 (wx) | w 또는 (xh) | x.

나는 O (n ^2/3) 알고리즘이 가능해야한다고 생각하지만 ... 나는 여기에 붙어있다!

---

편집 : 나는 그것을 해결할 수없는 생각 때문에 내가 포럼에 액세스 할 수 없습니다. 그래서 제가 도움을 청합니다. 나는 대부분의 다른 질문을 완료하고 태클을하고 싶습니다 이 질문을 지금!

편집 2 : 주요 요인으로 인한 영역이 막 다른 길이라 생각합니다. 왜냐하면 1 다른 영역이 있기 때문입니다. 프라임 영역이있는 사각형에는 0 개의 솔루션이 있고, 반투명 영역의 사각형에는 소수의 2 개가있는 경우 1 개의 솔루션이 있고 그렇지 않은 경우 0 개의 솔루션이 있습니다. 그러나 모든 반 패턴을 계산하는 것은 너무 오랜 시간이 걸릴 것입니다. 왜냐하면 2 * p 과 같이 모든 소수 p를 계산해야하기 때문에 가능하지 않습니다.

편집 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)을 셉니다. ! WH 및 XH | 마지막 이러한 합산 제약 0 < X < N, 0 < H < N + 1, X = H를 최대 (H, X ^2/H) < 1 + N <w은 X가 것 | h.

우리는 어떤 프라임 p가 x, w, h 또는 심지어 x-h를 나누고 다른 변수에 대해 우리가 추론 할 수있는 것을 알아야한다는 가정부터 시작해야한다고 생각합니다. 그 것이 잘 작동한다면 임의의 k에 대해 ^k을 고려해보십시오.

Answer 1

아직 해결책이 없지만 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)) 

분명히 무력 또는 가능하지 않습니다 12^10도 간단한 루프를 내놓았다,하지만 어쩌면이 알고리즘 하나는 어떤 점에서 닫힌 형태의 표현을 찾을 수 있습니다. num의 설정 문자가 아니라면 실행할 수 있습니다. 어쩌면이 방법으로 중복 지점을 찾을 수 있습니다.

이 막 다른 골목이 될 수 있지만, 여전히 파이썬이 표기에 사용되는 알고리즘 :

옆에 어떤 진전과 함께 작업 할 수 있습니다 꽤 멋진?