Tổng lớn nhất các số khác nhau có LCM bằng N trong C++

Cho số N, tìm tổng lớn nhất của các số khác nhau sao cho LCM của chúng bằng N.

Ví dụ: N=10 → ước số: 1,2,5,10. Tổng = 18.

Phương pháp

Tất cả các số trong tập hợp phải là ước của N (vì LCM = N). Để tổng lớn nhất, lấy tất cả ước số khác nhau của N. Tổng ước số = kết quả.

Duyệt i từ 1 đến √N, nếu i chia hết N thì cộng i và N/i (trừ khi i*i=N chỉ cộng một lần).

Ví dụ (C++)

#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+=i;
            else 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;
}

Đầu ra

The sum of distinct numbers with LCM as 42 is 96