简易华容道的移动规则与我国传统游戏华容道完全相同，不过棋盘可以是任意$m\times n$，而棋子则均只由大小相同的圆形筹码组成。

初始时棋盘上有$mn-1$个筹码，除右下角为空格外，其余每格中都恰有一个筹码，左上角的筹码为红色，其余为白色，游戏目的是将红色筹码移动到右下角。

下图片演示了$2\times 2$棋盘上五步完成游戏的过程。

记$S(m,n)$为$m\times n$棋盘上完成游戏所需的最少步数，例如可以验证$S(5,4)=25$。

若p是小于100的素数，则一共有$5482$种棋盘满足$S(m,n)=p^2$。

若p是小于$10^6$的素数，则共有多少种棋盘能满足$S(m,n)=p^2$？

本题难度:

解答

由于筹码的形状都一样，因此移动的策略很明确，简单尝试即可发现如下规律： $$s(m,n)=\begin{cases}6\max(m,n)+2\min(m,n)-13 & m\neq n, \\ 8m-11 & m=n. \end{cases}$$ 不难验证完全平方数模8不能余5，因此只需求$6\max(m,n)+2\min(m,n)-13$为$p^2$的数对m,n的数量。

固定$p$，不妨设$m>n>1$，与$m=(p^2+13-2n)/6$联立可得 $$\frac{p^2+13}{8} < m < \frac{p^2+11}{6},$$ 反之对此范围内的整数m，也能找到合适的n使得$6m+2n-13=p^2$。

因此枚举小于$10^6$的素数，对每个素数求出上述范围内的整数数量，汇总后即得结果$2057774861813004$。

target=1000000
d=[0]*target
n=2
while n < target:
    for i in range(n*n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1

print 2*sum((p*p+11)/6-((p*p+11)%6==0)-(p*p+13)/8+((p*p+13)%8==0) for p in range(2,target) if d[p]==0)