TechFUL: TechちゃんとFULちゃんのおねだり

問題概要

Tech ちゃんは 1 個  A 円のジュースを、FUL ちゃんは 1 個  B 円の板チョコを買いたい.

Tech ちゃんと FUL ちゃんはお金を持っていないため、お母さんからお小遣いを貰おうとした.

二人に対し、お母さんは次の3つの条件を満たすようなお小遣いを渡すと言った.

  1. Tech ちゃんと FUL ちゃんには同じ金額のお小遣いを渡す.

  2. Tech ちゃんと FUL ちゃんのそれぞれが必ず全ての金額をちょうど使い切れるだけのお小遣いを渡す.

  3. お小遣いの金額は  C 円以下.

お小遣いの通り数を求めよ.

制約

  •  1 \le A, B, C \le 10^{5}

解法

 x を条件 1 と 2 を満たす最小のお小遣いの金額とする.

このとき、 x A, B の最小公倍数となる.

最大公約数・最小公倍数の解説:AtCoder 版!マスター・オブ・整数 (最大公約数編) - Qiita

条件 1, 2, 3 を満たすお小遣いは  xk 円で表せる.

 k の範囲は  1 \le k \le \left\lfloor \frac{C}{x} \right\rfloor である.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    cout << C / lcm(A, B) << endl;
}