Tìm độ lịch sự (politeness) của một số trong C++

Trong bài toán này, cho số nguyên dương N. Nhiệm vụ là tìm độ lịch sự (politeness) của số.

Số lịch sự (Polite Number) là số biểu diễn được dưới dạng tổng của 2 hoặc nhiều số liên tiếp.

Độ lịch sự là số cách biểu diễn số đó dưới dạng tổng các số nguyên liên tiếp.

Ví dụ minh họa:

Đầu vào

n = 5

Đầu ra

1

Giải thích

2 + 3 = 5, là tổng liên tiếp duy nhất.

Phương pháp giải

Cách đơn giản: kiểm tra tất cả dãy liên tiếp đến N. Cách hiệu quả: dùng phân tích thừa số. Công thức: N = a^x * b^y * c^z... Độ lịch sự = [(x+1)*(y+1)*(z+1)...] - 1 (chỉ tính ước lẻ).

Chương trình minh họa:

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; 
}

Kết quả

Politeness of 13 is 1