note.txt

tongji acm-online judge solution

{
令ai为向量的系数
a1(p,q)+a2(p,-q)+a3(-p,q)+a4(-p,-q)+a5(q,p)+a6(q,-p)+a7(-q,p)+a8(-q,-p)=(x,y)
=>
(a1+a2-a3-a4)p+(a5+a6-a7-a8)q=dx (1)
(a5-a6+a7-a8)p+(a1-a2+a3-a4)q=dy (2)
令b1=a1-a4,b2=a2-a3,b3=a5-a8,b4=a6-a7
若确定整数bi，则ai一定有非负解。
(1)(2)=>
(b1+b2)p+(b3+b4)q=dx  (3)
(b3-b4)p+(b1-b2)q=dy  (4)
令x1=b1+b2,y1=b3+b4,x2=b3-b4,y2=b1-b2
x1p+y1q=dx (5)
x2p+y2q=dy (6)
不考虑x1,x2,y1,y2的是否有意义(bi可能非整数)，(5)(6)有解的充要条件为gcd(p,q)|dx且gcd(p,q)|dy (*)
因为b1=(x1+y2)/2,b2,b3,b4
所以(5)(6)有解的另一个必要条件为x1,y2同奇偶性且x2,y1同奇偶性(**)
(*)且(**)为问题有解的充要条件。
由extended_gcd
求出xp+yq=d 一个解(x,y)
令p'=p div d, q=q div d,dx'=dx div d,dy'=dy div d
xp+yq=d=>xp'+yq'=1
=>
(x*dx')p'+(y*dx')q'=dx'
(x*dy')p'+(y*dy')q'=dy'
解法1 ex.dpr
=>
x1=x*dx'+i*p'
y1=y*dx'-i*q'
x2=x*dy'+j*p'
y2=y*dy'-j*q'
由于(**)只考察奇偶性，故01枚举i,j检查x1+y2,y1+x2是否可以为偶数。
解法2 ex2.dpr
这时gcd(p',q')=1
所以(1)若p',q'一奇一偶，则一定可到(1,0)点,即可以遍历所有点。
(2)若p',q'一奇一奇，则一定不能到(1,0)点，但可一定能到(1,1)点,即可以遍历所有的偶点(x+y为偶数的点)。
}