ในปัญหานี้ เราได้รับจำนวนเต็มบวก 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
