Trong bài toán này, chúng ta được cung cấp một số nguyên dương N. Nhiệm vụ của chúng ta là tìm tính lịch sự của một số.
Số lịch sự là một số có thể được biểu thị bằng tổng của hai hoặc nhiều số liên tiếp.
Lịch sự của một số được định nghĩa là số cách con số có thể được biểu thị thành tổng của các số nguyên liên tiếp.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
n = 5
Đầu ra
1
Giải thích
2 + 3 = 5, is the only consecutive sum.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là kiểm tra tất cả các số liên tiếp cho đến N và nếu tổng của chúng bằng N, hãy tăng số đếm đó là tính lịch sự của số đó.
Giải pháp này không hiệu quả nhưng một giải pháp phức tạp nhưng hiệu quả là sử dụng phương pháp hóa bề mặt. Sử dụng công thức tính lịch sự thường là kết quả của số lượng các yếu tố lẻ, tức là
If the number is represented as N = ax * by * cz… Politeness = [(x + 1)*(y +1)*(z + 1)... ] - 1
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
Politeness of 13 is 1