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

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

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

制約： ，　

解法

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

計算時間：

#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;
}

すぐに証明できなかったけどA問題だからインクリメントすればいいだろうと実装してしまったので反省．
剰余を考えると見通しがよくなるのでメモ．