[BZOJ2299] [HAOI2011] 向量

题目

题目链接
题目大意为给你 a, b 问是否能用 (\pm a,\pm b)(\pm b, \pm a) 八组向量表达出向量(x,y)

 

思路

判断 x, y 是否分别能用 ak_1 + bk_2 的形式表达出来,可由裴蜀定理知 x 必须为 gcd(a, b) 的倍数才可以表示出来。
我们可以将 8 种向量归纳为两种操作:
1.只对 xy 其中一位有效的 (\pm 2a, 0), (\pm 2b, 0), (\pm 0, 2a), (\pm 0, 2b). 这种操作相当于可以对任意一位加减。
2.(a, b), (b, a). 仔细观察发现,这个两种操作分别至多只出现一次,当其出现偶数次时,效果相当于第一种操作的组合。
所以,我们可以枚举第二种操作的四种情况 (0, 0), (a, b), (b, a),(a+b, a+b)。之后再判断是否能由第一种操作得到。因为第一种操作 xy 是无关的,所以可以分开判断,而分开判断的标准就是之前说的裴蜀定理。

 

代码

 

完结

参考黄学长博客

发表评论

电子邮件地址不会被公开。 必填项已用*标注