각 쌍의 곱의 합

집합 X = {a, b, c}의 쌍별 곱은 가능한 모든 집합 쌍의 곱의 합으로 정의될 수 있습니다. 세트 쌍은 Y = {a * a, a * b, a *c, b * b, b * c, c * c}이며, 여기서 곱은 교환 가능합니다. 따라서 집합 X의 쌍별 곱은 집합 Y의 요소들의 합, 즉 aa + ab + ac + bb + bc + cc입니다.

수학적 용어로 가능한 쌍별 곱의 합은 다음과 같이 표현될 수 있습니다.

$$mathrm{displaystylesumlimits_{i=1,j=i}^{ileq n,jleq n}:(i,j)=itime j}$$

문제 설명

숫자 n이 주어졌습니다. n과 1을 포함하여 (1, n) 범위에서 쌍별 곱의 합을 구합니다.

예제 1

으아아아 으아아아

Explanation

의 중국어 번역은

Explanation

입니다.

i의 범위는 1~4이고, j의 범위는 i~4입니다.

1*1 + 1*2 + 1*3 + 1*4 + 2*2 + 2*3 + 2*4 + 3*3 + 3*4 + 4*4 = 1 + 2 + 3 + 4 + 4 + 6 + 8 + 9 + 12 + 16 = 65

예시 2

으아아아 으아아아

Explanation

의 중국어 번역은

Explanation

입니다.

i의 범위는 1~10이고, j의 범위는 i~10입니다.

1*1 + 1*2 + … + 1*10 + 2*2 + 2*3 + … + 2*10 + 3*3 + 3*4 + … + 3*10 + 4*4 + 4*5 + … 4*10 + 5*5 + 5*6 + … + 5*10 + 6*6 + 6*7 + … 6*10 + 7*7 + 7*8 + … 7*10 + 8* 8 + 8*9 + 8*10 + 9*9 + 9*10 + 10*10 = 1705

방법 1: 무차별 크래킹 방법

이 문제에 대한 무차별적인 해결책은 두 개의 for 루프를 사용하여 범위 내 가능한 모든 숫자 쌍을 반복하는 것입니다. 여기서 첫 번째 루프는 1에서 n까지 반복하고 두 번째 루프는 첫 번째 숫자에서 n까지 반복합니다.

의사코드

으아아아

예: C++ 구현

다음 프로그램에서는 가능한 모든 쌍을 찾은 다음 곱의 합을 구합니다.

으아아아

출력

으아아아

시간 복잡도 - O(n^2)

공간 복잡성 - O(1)

방법 2

n = 4를 예로 들어보겠습니다.

나는 = 1*1 + 1*2 + 1*3 + 1*4 + 2*2 + 2*3 + 2*4 + 3*3 + 3*4 + 4*4

위 내용을 단순화하면

나는 = 1*1 + (1+2)*2 + (1+2+3)*3 + (1+2+3+4)*4

prefix_sum[1] = 1을 취하세요.

접두사 합계[2] = 1+2,

접두사의 합[3] = 1+2+3,

접두사 합계[2] = 1+2,

의사코드

으아아아

예: C++ 구현

아래 프로그램에서는 각 반복의 합인 접두사 합계를 구하고, 여기에 반복 횟수를 곱한 다음 각 단계의 최종 합에 더합니다.

으아아아

출력

으아아아

결론

간단히 말하면, 1부터 n까지의 숫자 쌍곱의 합을 풀려면 위에서 언급한 두 가지 방법 중 하나를 사용할 수 있습니다. 첫 번째 방법은 무차별 방식이고 시간 복잡도는 O(n^ 2) 두 번째 방법은 Prefix sum을 이용하여 두 곱의 합을 계산하는 최적화 방법으로, 시간복잡도는 O(n)이다.

위 내용은 각 쌍의 곱의 합의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!