Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

각 요소가 N 이하인 고유한 숫자 쌍을 찾는 C++ 프로그램

이 글에서는 각 요소가 N보다 작거나 같으면서 아래 두 가지 조건을 동시에 만족하는 고유한 숫자 쌍을 찾는 C++ 프로그램에 대해 알아보겠습니다.

  • 두 수의 차이의 제곱이 그 두 수의 최소공배수(LCM)와 같아야 합니다.

  • 두 수의 최대공약수(HCF)가 연속된 두 자연수의 곱으로 표현될 수 있어야 합니다.

접근 방법

이 문제를 해결하는 가장 효율적인 방법은 연속된 두 자연수(1부터 시작)를 선택한 후, 그 두 수의 곱의 배수들을 구하는 것입니다. 그다음 배수들 중에서 하나의 쌍을 특정하기 위해, 쌍을 이루는 두 수가 첫 번째 조건을 만족하는지 검사하면 됩니다.

예를 들어 2와 3의 경우를 생각해 봅시다. 이 두 수의 곱은 6이고, 6의 배수를 나열하면 6, 12, 18, 24 … 와 같습니다. 이 배수들 중 두 수씩 짝지어 보면서, 인접한 두 수의 차이의 제곱(이 경우 62 = 36)이 해당 두 수의 LCM과 일치하는지 확인합니다. 그 결과 이 경우의 정답 쌍은 12와 18임을 알 수 있습니다.

이 과정을 일반화하면 두 수는 각각 Z × (Z × (Z+1))와 (Z+1) × (Z × (Z+1))이 됩니다. 여기서 Z는 최대공약수(HCF)를 구성하는 연속된 두 수 중 첫 번째 수입니다.

마지막으로 모든 값이 N 이하라는 조건을 적용하면 다음 부등식을 얻습니다.

(Z+1) × (Z × (Z+1)) ≤ N, 즉 Z3 + 2Z2 + Z ≤ N

예제 코드

#include <iostream>
using namespace std;
int main() {
    int N = 489, pairs, i = 1;
    //N 이하의 요소를 가진 쌍의 개수 계산
    while((i*i*i) + (2*i*i) + i <= N) {
        i++;
    }
    pairs = i;
    cout << "Pairs :" << endl;
    //쌍을 이루는 두 요소 출력
    for(int j = 1; j < pairs; j++) {
        cout << j*(j*(j+1)) << " " << (j+1)*(j*(j+1)) << endl;
    }
    return 0;
}

출력 결과

Pairs :
2 4
12 18
36 48
80 100
150 180
252 294
392 448

동작 원리 검증

출력된 첫 번째 쌍 (2, 4)을 직접 확인해 보면, 두 수의 차이는 2이고 그 제곱은 4이며, LCM(2, 4) 역시 4로 첫 번째 조건을 만족합니다. 또한 HCF(2, 4) = 2 = 1 × 2로 연속된 두 수의 곱으로 표현되므로 두 번째 조건도 충족합니다. 마찬가지로 (12, 18)의 경우 차이의 제곱은 36이고 LCM(12, 18) = 36, HCF는 6 = 2 × 3으로 두 조건을 모두 만족합니다.

while 반복문은 위에서 유도한 부등식 Z3 + 2Z2 + Z ≤ N을 이용해 가능한 쌍의 개수를 빠르게 계산하며, 이후 for 반복문이 일반화 공식에 따라 실제 쌍들을 출력합니다. 전체 시간 복잡도는 O(N1/3)으로 매우 효율적입니다.