龟速AK，%%% 7_dp_[0][0]_3，%%% 🐱🚀 两位神仙
T1
显然地，我们知道了 i,j,k,z,ni,j,k,z,ni,j,k,z,n 之后，可以求出 ppp，所以只需要一个四重循环。
Code:
T2
看到质数有关的，先打一个欧拉筛上去。时间复杂度：O(n)O(n)O(n).
这样我们得到了所有不超过 nnn 的质数。数位分离一下，计算和并取模即可。
Code:
T3
（显然的）kkk 是 A,BA,BA,B 的公约数。
所以我们枚举 gcd(A,B)\gcd(A,B)gcd(A,B) 的所有约数就好了。
注意只枚举到 gcd(A,B)\sqrt{\gcd(A,B)}gcd(A,B) 即可。因为约数成对出现。
特判完全平方数的情况。
Code:
T4
枚举垂足点 iii。
如果我们知道另一个点 jjj，那么我们可以知道构成直角三角形的点 kkk 在某条直线上。
所以我们对于每一个 jjj，记录一下它的向量如何表示。
然后统计 kkk 的数量。
由于三角形算了两遍，记得除以 222。
Code:
T5
首先我们对于每一个位置记录四方向是否可达。
我们知道，如果 {i,j) 可达 (k,l)(k,l)(k,l)，并且 (k,l)(k,l)(k,l) 可达 (i,j)(i,j)(i,j)，那么我们才能从这里走过去。（观察样例解释可以得到）
这就很好写了。
Code:
T6
普通的 DP 很容易想出来，刷表法就行了。
优化：注意到每一次跳跃的距离永远在 [d−400,d+400][d-400,d+400][d−400,d+400] 之间，所以优化成 O(800N)O(800N)O(800N) 能过了。
为什么？
我不知道啊，感觉是一个神秘的东西。
Code:
