CF 449E Jzzhu and Squares解题报告

题目大意


给定一个N*M的网格。对一个顶点为格点的正方形R(不一定与格线平行),计算出其中有多少个单位格被R完全包含(记作F(R))。求所有正方形的F(R)之和。

题解

首先画一个“勾股图”:



粉色是我们的正方形(不和格线平行),设其外接正方形的边长为L,四周直角三角形的短边为a,则长边为L-a。设其中完整包含了F(L,a)个单位格。

可以发现,其中完全包含的单位正方形分成两部分:第一部分是中间小正方形里的个,第二部分是周边直角三角形里包含的。

我们这么计算第二部分:一红一白两个直角三角形拼成的矩形内有(L-a)*a个单位格,而对角线穿过了L-gcd(L,a)格,再除以2,就得到了一个三角形内的单位格数。将其乘以4,总共加起来得到:



没错,“斜线下方的格点数”没有简单公式,但“单位格数”有!

可以发现,F(L,a)即使当a>L-a时也成立,所以我们可以直接用a枚举到底,整道题目的答案就是:



我们把展开:



这分成两部分:第一部分是一个关于L的多项式,第二部分是gcd(L,a)的前缀和。

可以想象,也是如此分成两部分:第一部分是一个关于L的多项式(确切地说,是5次多项式),第二部分也是一个关于L的“多项式”,但其“未知数项”不是这种形式,而是这种形式。

至于怎么得到这个多项式呢,如果你数学好可以手推……作为一名数学技能荒废一年的咸鱼选手,我就直接用vector当低配版多项式类,让电脑推了……

不要忘了,我们要求的是上面那个玩意的前缀和。因此,只需要求出来这两种形式关于L的“前缀和”,然后乘以多项式中相应的系数,就可以完成任务。

前者很简单:L不超过10^6,暴力递推即可。后者也差不多,只需要先递推出来phi函数,然后枚举gcd(a,L)的值,就可以把Σgcd的表都打出来,详见代码。

代码

发表评论

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