숫자 n과 다른 값 k가 있다고 가정하고 처음 N개의 자연수가 있는 배열 A가 있다고 가정하고 A에서 요소 A[i]와 A[j]의 총 쌍 수를 찾아야 합니다.
따라서 입력이 n =10 k =4와 같으면 합이 4로 나눌 수 있는 쌍이 10개 있기 때문에 출력은 10이 됩니다. [(1,3), (1,7), (2,6) , (2,10), (3,5), (3,9), (4,8), (5,7), (6,10), (7,9)]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- m :=(n / k)의 바닥, r :=n mod k
- b :=새 지도
- 0 ~ k - 1 범위의 i에 대해
- b[i] :=m
- m*k+1 ~ n 범위의 i에 대해
- j :=i 모드 k
- b[j] :=b[j] + 1
- c :=0
- 0~k 범위의 i에 대해
- i1 :=나는
- i2 :=(k - i) 모드 k
- i1이 i2와 같으면
- c :=c + b[i] *(b[i]-1)
- 그렇지 않으면
- c :=c + b[i1] *(b[i2])
- c/2의 반환 층
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(n, k):m =n // k r =n % k b ={} for i in range(k) :b[i] =m for i in range(m*k+1, n +1) :j =i % k b[j] =b[j] + 1 c =0 for i in range(k) :i1 =i i2 =(k - i) % k if i1 ==i2 :c =c + b[i] * (b[i]-1) else :c =c + b[i1] * (b[i2]) return c//2n =10k =4print(solve(n, k))입력
4, 27출력
10