N개의 숫자 목록이 있다고 가정합니다. 나머지 숫자의 GCD가 N개 숫자의 초기 GCD보다 크도록 필요한 숫자 제거의 최소 수를 찾아야 합니다.
따라서 입력이 [6,9,15,30]과 같으면 초기 gcd가 3이므로 출력이 2가 되므로 6과 9를 제거한 후 gcd를 15, 15> 3으로 얻을 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- INF :=100001
- spf :=요소가 0에서 INF인 목록
- sieve() 함수 정의
- 4~INF 범위의 i에 대해 2만큼 증가, do
- spf[i] :=2
- 범위 3에서 INF까지의 i에 대해
- i^2> INF -
- 중단
- spf[i]가 i와 같으면
- 범위 2 * i에서 INF까지의 j에 대해 i, do
- 로 각 단계에서 업데이트합니다.
- spf[j]가 j와 같으면
- spf[j] :=나
- spf[j]가 j와 같으면
- 범위 2 * i에서 INF까지의 j에 대해 i, do
- i^2> INF -
- calc_fact() 함수를 정의합니다. 시간이 걸립니다.
- ret :=새 목록
- x가 1과 같지 않은 동안 do
- ret 끝에 spf[x] 삽입
- x :=x / spf[x] (정수 부분만 가져오기)
- 반환
- 메인 방법에서 다음을 수행하십시오 -
- g :=0
- 0에서 n 사이의 i에 대해
- g :=gcd(a[i], g)
- my_map :=새 지도
- 0에서 n 사이의 i에 대해
- a[i] :=a[i] / g (정수 부분만 가져오기)
- 0에서 n 사이의 i에 대해
- p :=calc_fact(a[i])
- s :=새 지도
- 0~p 크기 범위의 j에 대해
- s[p[j]] :=1
- s의 각 i에 대해 다음을 수행합니다.
- my_map[i] :=my_map의 get(i, 0) + 1
- 최소 =10^9
- my_map의 각 i에 대해 다음을 수행합니다.
- 첫 번째 :=나
- 초 :=my_map[i]
- if (n - 초) <=최소값이면
- 최소 :=n - 초
- 최소값이 10^9가 아니면
- 최소 수익
- 그렇지 않으면
- 반환 -1
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from math import gcd as __gcd INF = 100001 spf = [i for i in range(INF)] def sieve(): for i in range(4, INF, 2): spf[i] = 2 for i in range(3, INF): if i**2 > INF: break if (spf[i] == i): for j in range(2 * i, INF, i): if (spf[j] == j): spf[j] = i def calc_fact(x): ret = [] while (x != 1): ret.append(spf[x]) x = x // spf[x] return ret def minRemove(a, n): g = 0 for i in range(n): g = __gcd(a[i], g) my_map = dict() for i in range(n): a[i] = a[i] // g for i in range(n): p = calc_fact(a[i]) s = dict() for j in range(len(p)): s[p[j]] = 1 for i in s: my_map[i] = my_map.get(i, 0) + 1 minimum = 10**9 for i in my_map: first = i second = my_map[i] if ((n - second) <= minimum): minimum = n - second if (minimum != 10**9): return minimum else: return -1 a = [6, 9, 15, 30] n = len(a) sieve() print(minRemove(a, n))
입력
[6, 9, 15, 30], 4
출력
2