ผลรวมสูงสุดของตัวเลขที่แตกต่างโดยมี LCM เป็น N ใน C++

ในปัญหานี้ เราได้รับหมายเลข N หน้าที่ของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดของตัวเลขที่ไม่ซ้ำกับ LCM เป็น N ใน C++

คำอธิบายปัญหา

ในที่นี้ เราต้องหาผลรวมของจำนวนสูงสุดที่มี N เป็นตัวคูณร่วมน้อย (LCM)

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

N = 10

ผลลัพธ์

18

คำอธิบาย

Maximum sum with LCM 10 is 1 + 2 + 5 + 10 = 18

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาอย่างง่ายคือการใช้แนวคิดที่ว่าถ้าเราต้องการตัวเลข N เป็น LCM เราจำเป็นต้องนำตัวหารเฉพาะของ N มาบวกกันเพื่อให้ได้ผลรวมสูงสุด

สำหรับสิ่งนี้ เราจะหาตัวประกอบทั้งหมดของ N แล้วนำมารวมกัน จะได้ค่าสูงสุดเมื่อเราพิจารณาตัวเลขทั้งหมดที่สามารถส่งผลให้ LCM เป็น N ได้

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <iostream>
using namespace std;

int calcFactorSum(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 = 42;
   cout<<"The sum of distinct numbers with LCM as "<<N<<" is "<<calcFactorSum(N);
   return 0;
}

ผลลัพธ์

The sum of distinct numbers with LCM as 42 is 96