주어진 두 숫자가 우호적인 쌍인지 확인합니다.

우호수 − 정수 이론에 따르면 우호수는 동일한 풍부 지수를 갖는 두 개 이상의 숫자입니다.

부유도 지수 - 자연수의 풍부도 지수는 자연수의 모든 약수의 합과 자연수 자체 간의 비율로 정의할 수 있습니다.

숫자 n의 풍부함은 $mathrm{frac{sigma(n)}{n}}$로 표현될 수 있습니다. 여기서 $mathrm{sigma(n)}$는 n의 모든 약수와 동일한 제수 함수를 나타냅니다.

예를 들어 자연수 30의 풍요지수는

$$mathrm{frac{sigma(30)}{30}=frac{1+2+3+5+6+10+15+30}{30}=frac{72}{ 30}=frac{12} {5}}$$

숫자 m mn이 있는 경우 숫자 n을 "친숙한 숫자"라고 합니다.

$mathrm{frac{시그마(m)}{m}=frac{시그마(n)}{n}}$

우호 쌍 − 동일한 잉여 지수를 갖는 두 숫자를 "우호 쌍"이라고 합니다.

문제 설명

Num1과 Num2라는 두 개의 숫자가 주어졌습니다. 두 숫자가 우호적인 쌍이 아닌 경우 반환됩니다.

예 1

으아악 으아악

Explanation

의 중국어 번역은

Explanation

입니다.

$$mathrm{frac{sigma(30)}{30}=frac{1+2+3+5+6+10+15+30}{30}=frac{72}{ 30}=frac{12} {5}}$$

$$mathrm{분수{시그마(140)}{140}=분수{1+2+4+5+7+10+14+20+28+35+70+140}{140 }=분수{336} {140}=분수{12}{5}}$$

frac{sigma(30)}{30}=frac{sigma(140)}{140}이므로 30과 140은 한 쌍의 친근한 숫자입니다.

예시 2

으아악 으아악

Explanation

의 중국어 번역은

Explanation

입니다.

$$mathrm{frac{sigma(5)}{5}=frac{1+5}{5}=frac{6}{5}=frac{6}{5}} $$

$$mathrm{frac{sigma(24)}{24}=frac{1+2+3+4+6+8+12+24}{24}=frac{60}{ 24}=frac{15} {6}}$$

$mathrm{frac{sigma(5)}{5}neqfrac{sigma(24)}{24}}$부터 5와 24는 우호적인 쌍이 아닙니다. p>

방법 1: 무차별 대입 방법

이 문제를 해결하는 무차별적인 방법은 먼저 두 숫자의 모든 약수의 합을 구한 다음 풍부 지수의 값을 계산하고 비교하여 결과를 얻는 것입니다.

의사코드

으아악

예: C++ 구현

아래 프로그램에서는 모든 약수의 합을 계산하여 풍요지수를 구합니다.

으아악

출력

으아악

시간 복잡도 - O(n) 왜냐하면 sumOfDivisors() 함수가 루프를 통과하기 때문입니다

공간 복잡성 - O(1)

방법 2: 풍요지수의 축약형

풍부도 지수의 단순화된 형태는 분자와 분모를 최대공약수로 나누어 구할 수 있습니다. 그런 다음 풍부함의 축약형이 같은지, 즉 분자와 분모가 같은지 확인하여 두 숫자가 우호적인 쌍인지 확인합니다.

의사코드

으아악

예: C++ 구현

다음 프로그램에서는 분자와 분모를 비교하여 두 숫자의 약식 존재비 지수가 동일한지 확인합니다.

으아악

출력

으아악

시간 복잡도 - sumOfDivisors() 함수의 시간 복잡도는 O(n^1/2log2n)입니다.

공간 복잡성 - O(1)

결론

결론적으로, 우호적 쌍이란 존재비 지수가 동일한 두 자연수, 즉 숫자 자체에 대한 모든 약수 합계의 비율을 의미합니다. 두 숫자가 친숙한 쌍인지 확인하려면 시간 복잡도가 O(n)인 무차별 솔루션과 시간 복잡도가 O(n^1/2log2n)인 최적화 솔루션을 지정하여 위의 접근 방식을 따르세요.

위 내용은 주어진 두 숫자가 우호적인 쌍인지 확인합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!