#902. [CZOI 2024 区域选拔 F] 律动石阶

[CZOI 2024 区域选拔 F] 律动石阶

题面背景

在古老的寺庙里,一条由石阶铺就的小径蜿蜒而上,通往寺庙的深处。沿途,石阶两旁开满了盛开的桃花,微风吹过,花瓣飘落,如同粉色的雨露洒落在大地。

你惊讶地发现,这些石阶竟然是用废墟的石料再利用铺就的,上面残留着荒废前刻下的文字。辨认这些文字,你感到这些石阶都承载着岁月的沉淀,历经风雨,沧桑而又庄严。

题目描述

石阶可以看作一个,南北 nn 格,东西 mm 格(n×mn\times m)的方阵。西北角 (1,1)(1,1) 的高度为 11。在同一排石阶(即东西走向)上的每个石阶高度比西边的石阶高 11,在同一列石阶(即南北走向)上每个石阶的高度比北边高 11。凝望着这片高高低低,充满历史沉重感的美景,你心生感慨,你想知道在这片律动的石阶上,有多少个位置的高度恰好等于 kk 呢?

输入格式

第一行包含三个整数分别表示,表示石阶南北的长度 nn、石阶东西的宽度 mm,以及目标高度 kk

输出格式

输出一个整数,表示满足条件的位置数量。

3 4 4
3

样例解释

在给定的 3×43 \times 4 的石阶中,记西北角为 (1,1)(1,1) 东南角为 (n,m)(n,m),有 33 个位置的高度等于 44,这三个位置分别是 (1,4)(2,3)(3,2)(1, 4)、(2, 3)、(3, 2)

数据规模及约定

对于 50%50\%n,m108,k<n×mn,m\leq 10^8,k<n\times m

对于 100%100\%n,m1018,k<n×mn,m\leq 10^{18},k<n\times m

保证至少有一个满足条件的位置。

保证测试编号为奇数的测试点,n=mn=m