초사각형은 k 차원을 갖는 직사각형입니다. 각 차원의 길이는 n1, n2, n3,....., nm로 표시할 수 있습니다. 초사각형의 셀은 (p,q,r,...)로 지정되며 (p,q,r,...)의 gcd와 동일한 값을 포함합니다. 여기서 1 <=p <=n1, 1 <=q <=n1 등입니다. 우리의 임무는 모든 셀 값 gcd(p,q,r,...)의 합을 결정하는 것입니다. 결과는 모듈로 10^9 + 7로 반환됩니다. 인덱싱은 1에서 n까지 수행됩니다.
따라서 입력이 input_arr =[[2, 2], [5, 5]]와 같으면 출력은 [5, 37]
두 개의 인스턴스가 입력으로 제공되며 이 두 개의 인스턴스에 대한 합을 결정해야 합니다. 각 경우에 초사각형은 4x4 2차원 직사각형이며 길이가 지정됩니다. 주소(p,q)와 gcd(p,q)는 다음과 같습니다 -
(p,q) value gcd(p,q) (1, 1) (1, 2) 1 1 (2, 1) (2, 2) 1 2
gcd의 합계 =1 + 1 + 1 + 2 =5
두 번째 경우 -
(p,q) value gcd(p,q) sum(gcd of row i) (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) 1 1 1 1 1 = 5 (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) 1 2 1 2 1 = 7 (3, 1) (3, 2) (3, 3) (3, 4) (3, 5) 1 1 3 1 1 = 7 (4, 1) (4, 2) (4, 3) (4, 4) (4, 5) 1 2 1 4 1 = 9 (5, 1) (5, 2) (5, 3) (5, 4) (5, 5) 1 1 1 1 5 = 9
gcd의 합계 =5 + 7 + 7 + 9 + 9 =37
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
coeff_find() 함수를 정의합니다. test_instance가 필요합니다.
- 값:=1
- test_instance의 각 k에 대해 다음을 수행합니다.
- 값 :=값 * (k / i)의 부동 소수점 값
- 반환 값
- 메인 메소드/함수에서 다음을 수행하십시오 -
- 출력:=새 목록
- input_arr의 각 test_instance에 대해 다음을 수행합니다.
- min_value :=test_instance의 최소값
- 총 값 :=0
- temp_dict :=새 지도
- 최소값에서 0까지의 범위에 있는 i에 대해 1만큼 감소, 수행
- p :=coeff_find(test_instance, i)
- q :=나
- q <=min_value 동안 수행
- q :=q + i
- q가 temp_dict에 있으면
- p :=p - temp_dict[q]
- temp_dict[i] :=p
- total_value :=total_value + temp_dict[i]*i
- 목록 출력 끝에 (total_value mod (10^9 + 7)) 추가
- 반환 출력
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def coeff_find(test_instance, i):
value = 1
for k in test_instance:
value *= k // i
return value
def solve(input_arr):
output = []
for test_instance in input_arr:
min_value = min(test_instance)
total_value = 0
temp_dict = {}
for i in range(min_value, 0, -1):
p = coeff_find(test_instance, i)
q = i
while q <= min_value:
q += i
if q in temp_dict:
p -= temp_dict[q]
temp_dict[i] = p
total_value += temp_dict[i]*i
output.append(total_value % (10**9 + 7))
return output
print(solve([[2, 2], [5, 5]])) 입력
[[2, 2], [5, 5]]
출력
[5, 37]