ในปัญหานี้ เราได้รับจำนวนเต็มบวก N งานของเราคือหาความสุภาพของตัวเลข
Polite Number คือตัวเลขที่สามารถแสดงเป็นผลรวมของตัวเลขต่อเนื่องสองตัวขึ้นไปได้
Politeness of a number ถูกนิยามว่าเป็นจำนวนวิธีที่ตัวเลขสามารถแสดงเป็นผลรวมของจำนวนเต็มต่อเนื่องได้
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input
n = 5
Output
1
อธิบาย
2 + 3 = 5 เป็นผลรวมต่อเนื่องเพียงวิธีเดียว
วิธีแก้ปัญหา
วิธีแก้ที่ง่ายคือตรวจสอบตัวเลขต่อเนื่องทั้งหมดจนถึง N และถ้าผลรวมเท่ากับ N ให้เพิ่มจำนวนนับซึ่งเป็น politeness ของตัวเลข
วิธีนี้ไม่มีประสิทธิภาพ แต่มีวิธีที่ซับซ้อนแต่มีประสิทธิภาพมากกว่าคือใช้การแยกตัวประกอบ (factorization) โดยใช้สูตรสำหรับ politeness ซึ่งเป็นผลคูณของจำนวนตัวประกอบคี่ คือ
ถ้าตัวเลขแทนได้เป็น N = a^x * b^y * c^z... 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
