[HAOI2011]向量（裴蜀定理）c/c++qq45739057的博客-

• 注释：本章同余针对
  $2$

  2。

• 题面
• 题意：见题面。
• 解决思路：考虑前四个向量
  $small (a,b), (a,-b), (-a,b), (-a,-b)$

  (a,b),(a,−b),(−a,b),(−a,−b)，设共取出
  $small n$

  n个向量，
  $small a,-a,b,-b$

  a,−a,b,−b的个数分别为
  $x_{a1},x_{a2},y_{b1},y_{b2}$

  xa1​,xa2​,yb1​,yb2​。
  
  $small begin{cases} x_{a1}+x_{a2}=n\ y_{b1}+y_{b2}=n\ end{cases}$

  { xa1​+xa2​=n yb1​+yb2​=n​
  
  $small n$

  n个向量之和为
  $small (ax_{a1}-ax_{a2},by_{b1}-by_{b2})$

  (axa1​−axa2​,byb1​−byb2​)
  设
  $small x_1=x_{a1}-x_{a2}$

  x1​=xa1​−xa2​，
  $small y_1=y_{b1}-y_{b2}$

  y1​=yb1​−yb2​，证明
  $small x_1equiv y_1$

  x1​≡y1​
  
  $small nequiv p$

  n≡p，
  $small p$

  p的取值为
  $small 0$

  0或
  $small 1$

  1
  
  $small therefore begin{cases} x_{a1}+x_{a2}equiv p\ y_{b1}+y_{b2}equiv p\ end{cases}$

  ∴{ xa1​+xa2​≡p yb1​+yb2​≡p​
  
  $small therefore begin{cases} x_{a1}+x_{a2}-2x_{a2}equiv p\ y_{b1}+y_{b2}-2y_{b2}equiv p\ end{cases}$

  ∴{ xa1​+xa2​−2xa2​≡p yb1​+yb2​−2yb2​≡p​
  
  $small therefore begin{cases} x_{a1}-x_{a2}equiv p\ y_{b1}-y_{b2}equiv p\ end{cases}$

  ∴{ xa1​−xa2​≡p yb1​−yb2​≡p​
  
  $small therefore x_1equiv y_1equiv p$

  ∴x1​≡y1​≡p
  证毕
  $small ！！！$

  ！！！
  结论：
  $small n$

  n个向量之和为
  $small (ax_1,by_1)$

  (ax1​,by1​)，
  $small x_1equiv y_1$

  x1​≡y1​
  同理考虑后四个向量
  $small (b,a), (b,-a), (-b,a), (-b,-a)$

  (b,a),(b,−a),(−b,a),(−b,−a)，设共取出
  $small m$

  m个向量，设
  $small m$

  m个向量之和为
  $small (by_2,ax_2)$

  (by2​,ax2​)，且
  $small y_2equiv x_2$

  y2​≡x2​
  八个向量之和为
  $small (ax_1+by_2,by_1+ax_2)$

  (ax1​+by2​,by1​+ax2​)，
  $small x_1equiv y_1$

  x1​≡y1​，
  $small y_2equiv x_2$

  y2​≡x2​
  
  $small therefore begin{cases} ax_1+by_2=x~~~~~~small x_1equiv y_1\ by_1+ax_2=y~~~~~~small y_2equiv x_2\ end{cases}$

  ∴{ ax1​+by2​=x      x1​≡y1​ by1​+ax2​=y      y2​≡x2​​
  
  $small therefore begin{cases} ax_1+by_2=x~~~~~~small x_1equiv y_1\ ax_2+by_1=y~~~~~~small y_2equiv x_2\ end{cases}$

  ∴{ ax1​+by2​=x      x1​≡y1​ ax2​+by1​=y      y2​≡x2​​
  情况一：
  $small x_1equiv y_1equiv 0$

  x1​≡y1​≡0，
  $small y_2equiv x_2equiv 0$

  y2​≡x2​≡0
  
  $small therefore begin{cases} ax_1+by_2=x\ ax_2+by_1=y\ end{cases}$

  ∴{ ax1​+by2​=x ax2​+by1​=y​
  将同余
  $small 0$

  0的项提出
  $small 2$

  2
  
  $small therefore begin{cases} 2ax_1’+2by_2’=x\ 2ax_2’+2by_1’=y\ end{cases}$

  ∴{ 2ax1′​+2by2′​=x 2ax2′​+2by1′​=y​
  有解的条件是
  $small (2a,2b)mid x$

  (2a,2b)∣x，
  $small (2a,2b)mid y$

  (2a,2b)∣y
  情况二：
  $small x_1equiv y_1equiv 0$

  x1​≡y1​≡0，
  $small y_2equiv x_2equiv 1$

  y2​≡x2​≡1
  
  $small therefore begin{cases} ax_1+by_2=x\ ax_2+by_1=y\ end{cases}$

  ∴{ ax1​+by2​=x ax2​+by1​=y​
  将同余
  $small 0$

  0的项提出
  $small 2$

  2
  
  $small therefore begin{cases} 2ax_1’+by_2=x\ ax_2+2by_1’=y\ end{cases}$

  ∴{ 2ax1′​+by2​=x ax2​+2by1′​=y​
  
  $small therefore begin{cases} 2ax_1’+b(y_2+1)=x+b\ a(x_2+1)+2by_1’=y+a\ end{cases}$

  ∴{ 2ax1′​+b(y2​+1)=x+b a(x2​+1)+2by1′​=y+a​
  
  $small therefore begin{cases} 2ax_1’+2by_2’=x+b\ 2ax_2’+2by_1’=y+a\ end{cases}$

  ∴{ 2ax1′​+2by2′​=x+b 2ax2′​+2by1′​=y+a​
  有解的条件是
  $small (2a,2b)mid (x+b)$

  (2a,2b)∣(x+b)，
  $small (2a,2b)mid (y+a)$

  (2a,2b)∣(y+a)
  同理
  情况三：有解的条件是
  $small (2a,2b)mid (x+a)$

  (2a,2b)∣(x+a)，
  $small (2a,2b)mid (y+b)$

  (2a,2b)∣(y+b)
  情况四：有解的条件是
  $small (2a,2b)mid (x+a+b)$

  (2a,2b)∣(x+a+b)，
  $small (2a,2b)mid (y+a+b)$

  (2a,2b)∣(y+a+b)

• AC代码

//优化 #pragma GCC optimize(2) //C #include<string.h> #include<stdio.h> #include<stdlib.h> #include<math.h> //C++ //#include<unordered_map> #include<algorithm> #include<iostream> #include<istream> #include<iomanip> #include<climits> #include<cstdio> #include<string> #include<vector> #include<cmath> #include<queue> #include<stack> #include<map> #include<set> //宏定义 #define N 1010 #define DoIdo main //#define scanf scanf_s #define it set<ll>::iterator //定义+命名空间 typedef long long ll; typedef unsigned long long ull; const ll mod = 998244353; const ll INF = 1e18; const int maxn = 1e6 + 10; using namespace std; //全局变量 //函数区 ll max(ll a, ll b) { return a > b ? a : b; } ll min(ll a, ll b) { return a < b ? a : b; } ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); } //主函数 int DoIdo() {       ios::sync_with_stdio(false);     cin.tie(NULL), cout.tie(NULL); int T;     cin >> T; while (T--) {         ll a, b, x, y;         cin >> a >> b >> x >> y;           ll g = gcd(2 * a, 2 * b); bool jg = 0; if (x % g == 0 && y % g == 0) jg = 1; if ((x + a) % g == 0 && (y + b) % g == 0) jg = 1; if ((x + b) % g == 0 && (y + a) % g == 0) jg = 1; if ((x + a + b) % g == 0 && (y + a + b) % g == 0) jg = 1; if (jg) cout << "Y" << endl; else cout << "N" << endl; } return 0; } //分割线---------------------------------QWQ /*       */