题解：P1945 无边的网格

· · 题解

这个题真不纯纯小学数学吗。这真不比「小学数学 N 合一」简单吗。

先把这个看起来就很搞笑的三角形做掉。

我记得有个小奥经典结论是格点正三角是不存在的，想一下咋证来着。

首先格点三角形我们有鞋带公式，所以面积是有理数。

然后正三角面积公式 S = \frac{\sqrt{3}}{4} a^2，如果在格点上那么边长的平方刚好把距离公式的根号消掉，于是因为 \sqrt 3 所以 S 是无理数，因此正三角必不在格点上。

然后就是数正方形。这个我记得也是小学就教的但是忘了，重推一遍。

正常的横平竖直的正方形数量是容易求出的，每个边长为 k 的横平竖直正方形又会贡献 k-1 个歪歪扭扭的正方形，所以总数量为 \sum_{i=0}^{\min(n,m)-1}(i+1)(n-i)(m-i)。

令 x=\min(n,m)，推。

\begin{aligned} \sum_{i=0}^{x-1}(i+1)(n-i)(m-i) &=\sum_{i=0}^{x-1}(inm+i^3-i^2(n+m))+\sum_{i=0}^{x-1}(nm+i^2-i(n+m)) \\ &=\frac{x(x-1)nm}2+\frac{x^2(x-1)^2}4-\frac{x(x-1)(2x-1)(n+m)}6+xnm+\frac{x(x-1)(2x-1)}6-\frac{x(x-1)(n+m)}2\\ \end{aligned}

高精度直接做就好。

绷不住了高精度减法写挂调一早上。

signed main(){
    string n,m;
    cin>>n>>m;
    string x;
    if(bdx(n,m)<=0)x=n;
    else x=m;
    cout<<gjj(gjjian(gjj(gaojingchu(gjcheng(x,gjcheng(gjjian(x,"1"),gjcheng(n,m))),"2"),gaojingchu(gjcheng(gjcheng(x,x),gjcheng(gjjian(x,"1"),gjjian(x,"1"))),"4")),gaojingchu(gjcheng(x,gjcheng(gjjian(x,"1"),gjcheng(gjjian(gjcheng(x,"2"),"1"),gjj(n,m)))),"6")),gjjian(gjj(gjcheng(x,gjcheng(n,m)),gaojingchu(gjcheng(x,gjcheng(gjjian(x,"1"),gjjian(gjcheng("2",x),"1"))),"6")),gaojingchu(gjcheng(gjcheng(x,gjjian(x,"1")),gjj(n,m)),"2")))<<" 0";
    return 0;
}
// 珂朵莉‧诺塔‧瑟尼欧里斯比原先预计的多活了一阵子。
// 然而，到最后她仍在缇亚忒不知道的地方奋战至死了。

// 为了保护自己珍惜的同伴，她主动用尽能保有自我的时间，挥舞遗迹兵器……据闻是如此。