题面
(近似权威解释,但有某种理解)
如果我们能想出一个数字 p p p 满足可以构造出一个 p 2 ∗ p 2 p^2 *p^2 p 2 ∗ p 2 头衔的条件由一个大矩形得到满足。
因此,为了查询,我们可以拦截这个广场的左上角。
然后我们考虑建造一个小广场 面积是.. p ∗ p p*p p ∗ p
对于小方形 B k B_k B k
我们在位置 ( i , j ) (i,j) ( i , j ) 填 ( i + j + k ) m o d p (i+j+k)mod~p ( i + j + k ) m o d p （注意 这里所有的 i , j i,j i , j 都是 [ 0 , p − 1 ] [0,p-1] [ 0 , p − 1 ] 的）
用小方块填满巨大的方块
具体区分大方形。 p ∗ p p*p p ∗ p 的格子（单位格长 p p p )
那么我们在 P i , j P_{i,j} P i , j 放 B i ∗ j m o d p B_{i*j~mod~p} B i ∗ j m o d p
然后我们让你看看它是什么样子 p p p 它将适合主题的需要, 就此而言, p p p 为什么这种构造合法
首先,条件不能在一个或两个小广场上实现。
左上角和右下角坐标如下: ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2) ( x 1 , y 1 ) , ( x 2 , y 2 )
假设分别属于 a , b , c , d a,b,c,d a , b , c , d 四个小正方形里
那么
x
1
+
y
1
+
a
≡
x
2
+
y
1
+
c
(
m
o
d
p
)
x1+y1+a equiv x2+y1+c~(mod~p)
x
1
+
y
1
+
a
≡
x
2
+
y
1
+
c
(
m
o
d
p
)
x
2
−
x
1
≡
a
−
c
x2-x1 equiv a-c
x
2
−
x
1
≡
a
−
c
同理可得
x 2 − x 1 ≡ b − d x2-x1 equiv b-d x 2 − x 1 ≡ b − d
因此
a − c ≡ b − d ( m o d p ) a-c equiv b-d(mod~p) a − c ≡ b − d ( m o d p )
假设他们在大广场上 a = ( X 1 , Y 1 ) , d = ( X 2 , Y 2 ) a=(X_1,Y_1),d=(X_2,Y_2) a = ( X 1 , Y 1 ) , d = ( X 2 , Y 2 )
那么 X 1 Y 1 − X 2 Y 1 = X 1 Y 2 − X 2 Y 2 X_1Y_1-X_2Y_1=X_1Y_2-X_2Y_2 X 1 Y 1 − X 2 Y 1 = X 1 Y 2 − X 2 Y 2
所以 ( X 2 − X 1 ) ( Y 2 − Y 1 ) ≡ 0 ( m o d p ) (X_2-X_1)(Y_2-Y_1) equiv 0 pmod p ( X 2 − X 1 ) ( Y 2 − Y 1 ) ≡ 0 ( m o d p )
那么 如果 p p p 是一个质数 则 p p p 在左边,不得有公共因素。
因此上式不可能成立
所以 p p p 它是在顶峰时建造的。
那么因为要满足截取 n = 500 n=500 n = 5 0 0
所以当 p p p 取23<25（题目要求的上限）
可以构造出所有解