C++
 Computer >> コンピューター >  >> プログラミング >> C++

【C++】nより大きくkで割り切れる最小の整数を見つける方法

2つの整数 n と k が与えられたとします。このとき、n より大きく、かつ k で割り切れる最小の整数 x を求める必要があります。

例えば、入力が n = 5、k = 3 の場合、出力は 6 となります。6 は 5 より大きい数の中で、3 で割り切れる最小の整数だからです。

解法のアプローチ

この問題は、ループで候補を順番に調べることなく、次のシンプルな式を使うことで O(1) の計算量で解くことができます。

return n + k - (n % k)

なぜこの式が成り立つのか

n % k(n を k で割った余り)を引いてから k を足し戻すことで、n を超える最初の k の倍数が得られます。仮に n = qk + r(0 ≤ r < k)と表せると、計算結果は qk + r + k - r = (q+1)k となり、これは n より大きい最小の k の倍数です。また、n がすでに k の倍数の場合も余りが 0 になるため、正しく次の倍数である n + k が返されます。

実装例

理解を深めるために、以下の C++ 実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int n, int k){
    return n + k - n % k;
}
int main(){
    int n = 5;
    int k = 3;
    cout << solve(n, k) << endl;
}

入力

5, 3

出力

6
  1. C++でn番目のスターナンバー（星形数）を求めるプログラム

    この記事では、整数 n が与えられたときに、n番目のスターナンバー を求めるC++プログラムの作成方法を解説します。スターナンバーとは？スターナンバー（Star Number）とは、中心に点を置き、その周囲に六芒星（六角星）の形を描いたときの点の総数を表す特殊な数です。図形的には「中心付き六芒星数」と呼ばれることもあります。スターナンバーの例は以下の通りです。1, 13, 37, 73, 121, ...問題の理解具体的な入力と出力の例を見てみましょう。入力n = 5出力121n = 5 のとき、5番目のスターナンバーである 121 が出力されます。解法のアプローチn番目のスターナンバーは、次

  2. C++で数値の最大の素因数を求める方法

    ある整数 x が与えられたとき、その最大の素因数を求めることを考えます。例えば、x = 6 の場合、6 を素因数分解すると 2 × 3 となるため、最大の素因数は 3 です。 この問題は、対象の数を小さい約数から順に割り続けて素因数分解を行い、その過程で現れる素因数のうち最も大きいものを記録していくことで解くことができます。 アルゴリズムの流れ n が偶数である限り 2 で割り続け、素因数として 2 を記録します。 3 から √n までの奇数 i について、n が i で割り切れる限り割り続け、i を素因数として記録します。 ループ終了後も n が 2 より大きければ、残った n 自体が素