ในปัญหานี้ เราคือตัวเลข N หน้าที่ของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดของตัวเลขที่แตกต่างกัน โดยที่ LCM ของตัวเลขเหล่านี้เป็น N ใน C++
คำอธิบายปัญหา
เราต้องหาผลรวมของตัวประกอบทั้งหมดของจำนวน N แล้วบวกค่าที่ต่างกันทั้งหมดเพื่อหาผลรวมสูงสุด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
N = 12
ผลลัพธ์
28
คำอธิบาย
All distinct factors of N are 1, 2, 3, 4, 6, 12. Sum = 1 + 2 + 3 + 4 + 6 + 12 = 28
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือการหาตัวประกอบทั้งหมดของตัวเลข แล้วบวกตัวประกอบที่แตกต่างกันทั้งหมดเพื่อหาผลลัพธ์
สำหรับสิ่งนี้ เราจะวนซ้ำจนถึงรากที่สองของ N และตรวจสอบว่าตัวเลขหาร N หรือไม่ ถ้าใช่ ให้ตรวจสอบว่ามีความแตกต่างกันหรือไม่ ถ้าใช่ ให้เพิ่มตัวเลขและผลหารหาร มิฉะนั้น ให้เพิ่มตัวเลข ส่งคืนผลรวมสูงสุดสุดท้าย
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int calcMaxSumForLCM(int N){
int maxSum = 0;
for (int i = 1; i*i <= N; i++){
if (N%i == 0){
if (i == (N/i))
maxSum = maxSum + i;
else
maxSum = maxSum + i + (N/i);
}
}
return maxSum;
}
int main(){
int N = 17;
cout<<"The sum of distinct numbers such that LCM if these numbers is "<<N<<" is "<<calcMaxSumForLCM(N);
return 0;
} ผลลัพธ์
The sum of distinct numbers such that LCM if these numbers is 17 is 18
