Python에서 솔루션이 하나만 있는 선형 방정식의 계수를 찾는 프로그램

<시간/>

값 n이 있다고 가정하고 방정식 a*x + b*y =n이 최소한 하나의 해를 갖도록 존재하는 쌍 (a, b) [a

따라서 입력이 n =4와 같으면 유효한 쌍이 (1, 2) 및 (1, 3)이므로 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

divisors_gen() 함수를 정의합니다. n
divs :=n+1 크기의 목록 목록입니다. 그리고 각 내부 목록은 1을 보유하고 있습니다.
divs[0] :=요소가 하나만 있는 목록 0
2~n 범위의 i에 대해 다음을 수행합니다.
- (n / i) + 1의 바닥까지 범위 1의 j에 대해
  - 인덱스 [i * j]의 목록 끝에 i 삽입
div를 반환하지만 모든 내부 목록을 뒤집습니다.
메인 방법에서 다음을 수행하십시오. -
결과:=0
d_cache :=divisors_gen(n+1)
1에서 n - 1까지의 범위에 대해 다음을 수행합니다.
- i :=1
- s :=새로운 세트
- a*i
- b :=n - a*i
- d_cache[b]의 각 d에 대해 다음을 수행합니다.
  - d> a이면
    - d가 s에 없으면
      - 결과 :=결과 + 1
  - 그렇지 않으면
    - 루프에서 나오다
  - 세트 s에 d 삽입
- 나는 :=나는 + 1

반환 결과

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def divisors_gen(n):
   divs = [[1] for x in range(0, n + 1)]
   divs[0] = [0]
   for i in range(2, n + 1):
      for j in range(1, n // i + 1):
         divs[i * j].append(i)
   return [i[::-1] for i in divs]

def solve(n):
   result = 0
   d_cache = divisors_gen(n+1)

   for a in range(1, n):
      i = 1
      s = set([])
      while a*i < n:
         b = n - a*i
         for d in d_cache[b]:
            if d > a:
               if d not in s:
                  result += 1
            else:
               break
            s.add(d)
         i += 1
   return result

n = 4
print(solve(n))