問題一覧 > 通常問題

No.2043 Ohuton and Makura

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 126
作問者 : koboshikoboshi / テスター : 👑 KazunKazun 👑 hitonanodehitonanode
1 ProblemId : 8049 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-09 22:12:11

問題文

小星さんは座標平面上に敷布団と枕を用意して寝ることにしました。

敷布団は長方形 $\{(x,y)\in\mathbb{R}^2\mid 0\le x\le A, 0\le y\le B\}$ です。

枕は頂点が格子点である長方形であって、辺が $x$ 軸または $y$ 軸と平行なものです。

次の条件を満たす枕は何通りありますか。

  • 枕の面積は $1$ 以上 $S$ 以下
  • 枕は敷布団の上にある (すなわち枕が表す領域は敷布団が表す領域の部分集合である)

この問題の制約の下で、答えは $9\times 10^{18}$ 以下であることが証明可能です。

制約

  • $1\le A,B,S\le 5\times 10^5$
  • 入力はすべて整数

入力

$A$ $B$ $S$

出力

答えを出力してください。

サンプル

サンプル1
入力
3 4 2
出力
29

条件を満たす枕の一例です。青の長方形は敷布団、赤の長方形は枕を表します。

サンプル2
入力
1 1 100
出力
1

サンプル3
入力
100000 200000 300000
出力
59141508890785287

答えは大きくなる場合があります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。