โปรแกรม C++ หาจำนวนเต็มใกล้ที่สุดที่ GCD กับผลรวมหลักมากกว่า 1

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

สมมติว่าเรามีตัวเลข N พิจารณาฟังก์ชัน gcdSum(x) ของจำนวนเต็มบวก x ซึ่งเป็น GCD ของตัวเลขนั้นกับผลรวมหลักของมัน ต้องการหาจำนวนเต็ม x >= n ที่น้อยที่สุด ที่ทำให้ gcdSum(x) > 1

ตัวอย่าง: N = 31 ผลลัพธ์คือ 33 เพราะ GCD(31, 3+1)=1, GCD(32, 3+2)=1, GCD(33, 3+3)=3

ขั้นตอนการแก้ปัญหา

สำหรับ i := n ถึง n+2:
    jml := 0
    x := i
    while x > 0:
        jml := jml + x mod 10
        x := x / 10
    ถ้า GCD(i, jml) != 1:
        คืนค่า i
คืนค่า 0

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
    for (long i = n; i <= n + 2; i++) {
        long jml = 0;
        long x = i;
        while (x > 0) {
            jml += x % 10;
            x /= 10;
        }
        if (__gcd(i, jml) != 1) {
            return i;
        }
    }
    return 0;
}

int main() {
    int N = 31;
    cout << solve(N) << endl;
}

อินพุต

31

เอาต์พุต

33