ABC032 A問題：高橋君と青木君の好きな数

問題. 高橋君と青木君の好きな数

正の整数 $a, b, n$ が与えられる． $n$ 以上の $a$ と $b$ の公倍数で最小の数を求めよ．

制約： $1 \le a, b \le 100$ ，　 $1 \le n \le 20,000$

解法

$n$ を $a$ と $b$ の公約数になるまでインクリメントする．このとき，求める数は $n + a b - 1$ 以下となるので，インクリメントする数も高々 $a b - 1$ 回となる．
求める数が $n + a b - 1$ 以下となるのは $a b$ による剰余を考えると分かる．整数 $x$ が $a$ と $b$ の公約数となるための必要十分条件は $x$ の $a b$ による剰余が 0 となることである． $n \mod a b$ の値は 0 以上 $a b$ よりも小さいので，剰余が 0 となるために加える最小の値は高々 $a b - 1$ である．

計算時間： $O(a b)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int a, b, n;
    cin >> a >> b >> n;

    while (n % a != 0 || n % b != 0) ++n;
    cout << n << endl;

    return 0;
}