#P2987. Earthquake

    ID: 2108 传统题 1000ms 512MiB 尝试: 286 已通过: 104 难度: 7 上传者: 标签>CF2200提高+/省选-类欧几里得算法交换求和顺序向下取整与向上取整

Earthquake

Earthquake

题目描述

给定 a, b, ca,\,b,\,c ,求满足方程 ax+by⩽cax+by \leqslant c 的非负整数解个数。

输入格式

输入三个整数 a, b, ca,\,b,\,c 。

输出格式

输出一个整数表示答案。

样例 #1

样例输入 #1

3 4 13

样例输出 #1

12

提示

样例解释:

若以 (x, y)(x,\,y) 表示一组合法解,样例的 1212 组合法解如下:

(0, 0)(0,\,0),(0, 1)(0,\,1),(0, 2)(0,\,2),(0, 3)(0,\,3),(1, 0)(1,\,0),(1, 1)(1,\,1),(1, 2)(1,\,2),(2, 0)(2,\,0),(2, 1)(2,\,1),(3, 0)(3,\,0),(3, 1)(3,\,1),(4, 0)(4,\,0) 。

数据规模:

测试点编号 a, ba,\,b cc
1∼51 \sim 5 ⩽10\leqslant 10
6∼106 \sim 10 ⩽105\leqslant 10^5 ⩽109\leqslant 10^9
11∼2511 \sim 25 ⩽109\leqslant 10^9 ⩽1018\leqslant 10^{18}

对于所有数据,$1 \leqslant a,\,b \leqslant 10^9,\ 0 \leqslant c \leqslant \min(a,\,b) \times 10^9$ 。