Noip2017Day1T1小凯的疑惑

题目链接

NoipDay1T1小凯的疑惑

题解

考试的时候胆子比较大…三分钟看出一个神奇的公式直接\(long long\)上然后不管了…

废话名字叫数学,数据给一个亿一看,谁都知道是公式题……

这道题当时\(Wahacer\)出\(noip\)模拟赛的时候奶中过…

\(RP–\)

当时出的是\(usaco\)麦香牛块的加强版,是当时2002年冬令营的一道题….

与这道题类似….

这道题因为题目中强调了是给定的两个数字互质.

所以跟\(gcd\)有关系…

\(a,b\)满足 \( gcd(a,b)==1 \) ,则有\( px+qy=n \) 无非负整数解的最大正整数n为 \( a*b-a-b \)

用当时那道题的证明方法来证明.

以 5,7 为例子,答案应该是23.

第一竖列 第二竖列 第三竖列 第四竖列 第五竖列
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
26 27 28 29 30
31 32 33 34 35

可以发现第5竖列全部都是可以支付的.

第4竖列14以下都是可以支付的.

第1竖列21以下都是可以支付的.

第2竖列7以下都是可以支付的.

第3竖列28以下都是可以支付的.

我们综合上面的重新画图.能支付的用\(X\)表示

第一竖列 第二竖列 第三竖列 第四竖列 第五竖列
1 2 3 4 \(X\)
6 \(X\) 8 9 \(X\)
11 \(X\) 13 \(X\) \(X\)
16 \(X\) 18 \(X\) \(X\)
\(X\) \(X\) 23 \(X\) \(X\)
\(X\) \(X\) \(X\) \(X\) \(X\)
\(X\) \(X\) \(X\) \(X\) \(X\)

所以还存活的最大数字是23…

我们可以通过23下面的数字发现这个关系.

其实这个表格是以5个数字为一组分组的.

23下面的数字是28

\(28=(a-1)*b\)

23=28-5,\(b\)=5

所以答案就是\((a-1)*b-b\)

综合一下答案就是\(a*b-a-b\)喽…


By:Wahacer

2017.12.13

16:47

发表评论

电子邮件地址不会被公开。 必填项已用*标注