Chương trình C++ tìm số nguyên gần nhất có GCD với tổng chữ số lớn hơn 1

Cho số N. Hàm gcdSum(x) = GCD của x và tổng chữ số của x. Tìm x >= N nhỏ nhất sao cho gcdSum(x) > 1.

Ví dụ

Với N = 31, đầu ra 33. GCD(31,4)=1, GCD(32,5)=1, GCD(33,6)=3 > 1.

Giải thuật

Kiểm tra N, N+1, N+2. Với mỗi số, tính tổng chữ số, nếu GCD(số, tổng) > 1 thì trả về. Chứng minh: trong 3 số liên tiếp luôn có số chia hết cho 3, tổng chữ số cũng chia hết cho 3 → GCD ≥ 3.

Mã 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;
}

Đầu vào / Đầu ra

Input: 31
Output: 33