肯定先找规律,显然最后的空格在哪里不是我们关心的,所以f(n,m)具有对称性,我们采取手模的方式:
| f(n,m) | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 2 | 5 | 9 | 15 | 21 |
| 3 | 13 | 17 | 23 | |
| 4 | 21 | 25 | ||
| 5 | 29 |
发现斜角是+8,斜角第一直出是+4,之后都是+6.我们要在表内寻找 $p^2$ ,因为斜角增长是8,所以整张表会接近 $\frac{p^2_m}8$ ,Flu计算所有质数平方模6的后缀和,也就是说一个数字匹配上了之后整个剩余系中余数相同的也能匹配上,所以双指针l是斜角,r是质数,复杂度 $O(\frac{1e12}8)$ ,实际上跑了三分钟左右.
论坛里说直接把整个式子算出来(m>n有f(m,n)=8m+2n-13)然后对每个质数算贡献也行.