이 문제에서 양의 정수 N이 주어집니다. 우리의 임무는 숫자의 정중함을 찾는 것입니다.
폴라이트 넘버 두 개 이상의 연속된 숫자의 합으로 표현할 수 있는 숫자입니다.
숫자의 공손함 연속된 정수의 합으로 숫자를 표현할 수 있는 방법의 수로 정의됩니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
n = 5
출력
1
설명
2 + 3 = 5, is the only consecutive sum.
솔루션 접근 방식
문제에 대한 간단한 해결책은 N까지의 모든 연속된 숫자를 확인하고 그 합이 N과 같으면 숫자의 공손함인 개수를 늘리는 것입니다.
이 솔루션은 효율적이지는 않지만 복잡하지만 효율적인 솔루션은 인수분해를 사용하는 것입니다. 홀수 요인의 곱으로 발생하는 공손함의 공식을 사용합니다. 즉,
If the number is represented as N = ax * by * cz… Politeness = [(x + 1)*(y +1)*(z + 1)... ] - 1
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <iostream>
using namespace std;
int calcPolitenessNumber(int n){
int politeness = 1;
while (n % 2 == 0)
n /= 2;
for (int i = 3; i * i <= n; i += 2) {
int divCount = 0;
while (n % i == 0) {
n /= i;
++divCount;
}
politeness *= divCount + 1;
}
if (n > 2)
politeness *= 2;
return (politeness - 1);
}
int main(){
int n = 13;
cout<<"Politeness of "<<n<<" is "<<calcPolitenessNumber(n);
return 0;
} 출력
Politeness of 13 is 1