두 개의 숫자 A와 B가 있다고 가정합니다. 이제 각 연산에서 숫자 중 하나를 선택하고 1씩 증가하거나 1 감소할 수 있습니다. 우리는 최대 공약수가 되도록 필요한 최소 연산 수를 찾아야 합니다. A와 B 사이는 1이 아닙니다.
따라서 입력이 A =8, B =9와 같으면 출력은 1이 됩니다. 9를 선택한 다음 10으로 늘릴 수 있으므로 8과 10은 공소수가 아닙니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
및 b의 gcd가 1과 같지 않으면
-
0 반환
-
-
짝수이거나 b가 짝수이면
-
1 반환
-
-
그렇지 않으면
-
a + 1 및 b의 gcd가 1과 같지 않거나 a - 1 및 b의 gcd가 1과 같지 않거나 a 및 b - 1의 gcd가 1과 같지 않거나 a 및 b + 1의 gcd가 같지 않은 경우 1, 그 다음
-
1 반환
-
-
그렇지 않으면
-
2를 반환
-
-
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
from math import gcd class Solution: def solve(self, a, b): if gcd(a, b) != 1: return 0 if a % 2 == 0 or b % 2 == 0: return 1 else: if (gcd(a + 1, b) != 1 or gcd(a - 1, b) != 1 or gcd(a, b - 1) != 1 or gcd(a, b + 1) != 1): return 1 else: return 2 ob = Solution() A = 8 B = 9 print(ob.solve(A, B))
입력
8,9
출력
1