数値とその桁の合計gcdが1より大きい最も近い整数を検索するC++プログラム

数値Nがあるとします。正の整数xの関数gcdSum（x）を考えます。これは、その整数とその桁の合計のgcdです。 gcdSum（x）> 1となるような、最小の整数x>=nを見つける必要があります。

したがって、入力がN =31の場合、31のgcdと（3 + 1）は1であるため、出力は33になります。32のgcdと（3 + 2）は1であり、33のgcdと（ 3 + 3）は3です。

ステップ

これを解決するには、次の手順に従います-

for initialize i := n, when i <= n + 2, update (increase i by 1), do:
   jml := 0
   x := i
   while x > 0, do:
      jml := jml + x mod 10
      x := x / 10
   if gcd of i and jml is not equal to 1, then:
      return i
return 0

例

理解を深めるために、次の実装を見てみましょう-

#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