【CF774G】Perfectionist Arkadiy

目前CF 数论分类下AC人数最少的题目?(不过貌似我做完之后就不是了

好像推一推式子就可以得到一些奇妙算法

然后我翻了翻AC代码

发现一个非常短非常玄妙的代码

我把它整理了一下

md怎么好像

一行输入一行特判无解一行输出?

怎么这么短小啊?

想了很久推了很久。。突然发现这做法很naive啊根本不用推式子。。

首先把原来的矩阵长宽都拓宽\(a\),然后在拓宽出来的区域里也填上正方形

就像这样

那么每行每列都是若干个正方形+一条线组成的东西

也就是\((a+x)\)的若干倍

那么很明了了 就是求出最小的\((a+x)\),使得\((h+a)\)和\((w+a)\)除以它都能得到整数

那么只要\(g=(h+a,w+a)\)除以它是整数

假设\(\frac{g}{a+x}=y\),那么就是求满足\(\frac{g}{y}\ge a\)的最大\(y\)

显然是\(\lfloor\frac{g}{a}\rfloor\)

那么答案显然是\(\frac{g}{y}-a\)

说点什么

您将是第一位评论人!

提醒
wpDiscuz