[HAOI2011]向量(裴蜀定理)

  • 注释:本章同余针对222。
  • 题面
  • 题意:见题面。
  • 解决思路:考虑前四个向量(a,b),(a,b),(a,b),(a,b)\small (a,b), (a,-b), (-a,b), (-a,-b)(a,b),(a,−b),(−a,b),(−a,−b),设共取出n\small nn个向量,a,a,b,b\small a,-a,b,-ba,−a,b,−b的个数分别为xa1,xa2,yb1,yb2x_{a1},x_{a2},y_{b1},y_{b2}xa1​,xa2​,yb1​,yb2​。
    { xa1+xa2=n yb1+yb2=n\small \begin{cases} \ x_{a1}+x_{a2}=n\\ \ y_{b1}+y_{b2}=n\\ \end{cases}{ xa1​+xa2​=n yb1​+yb2​=n​
    n\small nn个向量之和为(axa1axa2,byb1byb2)\small (ax_{a1}-ax_{a2},by_{b1}-by_{b2})(axa1​−axa2​,byb1​−byb2​)
    x1=xa1xa2\small x_1=x_{a1}-x_{a2}x1​=xa1​−xa2​,y1=yb1yb2\small y_1=y_{b1}-y_{b2}y1​=yb1​−yb2​,证明x1y1\small x_1\equiv y_1x1​≡y1​
    np\small n\equiv pn≡p,p\small pp的取值为0\small 00或1\small 11
    { xa1+xa2p yb1+yb2p\small \therefore \begin{cases} \ x_{a1}+x_{a2}\equiv p\\ \ y_{b1}+y_{b2}\equiv p\\ \end{cases}∴{ xa1​+xa2​≡p yb1​+yb2​≡p​
    { xa1+xa22xa2p yb1+yb22yb2p\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​
    { xa1xa2p yb1yb2p\small \therefore \begin{cases} \ x_{a1}-x_{a2}\equiv p\\ \ y_{b1}-y_{b2}\equiv p\\ \end{cases}∴{ xa1​−xa2​≡p yb1​−yb2​≡p​
    x1y1p\small \therefore x_1\equiv y_1\equiv p∴x1​≡y1​≡p
    证毕\small !!!!!!
    结论:n\small nn个向量之和为(ax1,by1)\small (ax_1,by_1)(ax1​,by1​),x1y1\small x_1\equiv y_1x1​≡y1​
    同理考虑后四个向量(b,a),(b,a),(b,a),(b,a)\small (b,a), (b,-a), (-b,a), (-b,-a)(b,a),(b,−a),(−b,a),(−b,−a),设共取出m\small mm个向量,设m\small mm个向量之和为(by2,ax2)\small (by_2,ax_2)(by2​,ax2​),且y2x2\small y_2\equiv x_2y2​≡x2​
    八个向量之和为(ax1+by2,by1+ax2)\small (ax_1+by_2,by_1+ax_2)(ax1​+by2​,by1​+ax2​),x1y1\small x_1\equiv y_1x1​≡y1​,y2x2\small y_2\equiv x_2y2​≡x2​
    { ax1+by2=x      x1y1 by1+ax2=y      y2x2\small \therefore \begin{cases} \ ax_1+by_2=x~~~~~~\small x_1\equiv y_1\\ \ by_1+ax_2=y~~~~~~\small y_2\equiv x_2\\ \end{cases}∴{ ax1​+by2​=x      x1​≡y1​ by1​+ax2​=y      y2​≡x2​​
    { ax1+by2=x      x1y1 ax2+by1=y      y2x2\small \therefore \begin{cases} \ ax_1+by_2=x~~~~~~\small x_1\equiv y_1\\ \ ax_2+by_1=y~~~~~~\small y_2\equiv x_2\\ \end{cases}∴{ ax1​+by2​=x      x1​≡y1​ ax2​+by1​=y      y2​≡x2​​
    情况一x1y10\small x_1\equiv y_1\equiv 0x1​≡y1​≡0,y2x20\small y_2\equiv x_2\equiv 0y2​≡x2​≡0
    { ax1+by2=x ax2+by1=y\small \therefore \begin{cases} \ ax_1+by_2=x\\ \ ax_2+by_1=y\\ \end{cases}∴{ ax1​+by2​=x ax2​+by1​=y​
    将同余0\small 00的项提出2\small 22
    { 2ax1+2by2=x 2ax2+2by1=y\small \therefore \begin{cases} \ 2ax_1'+2by_2'=x\\ \ 2ax_2'+2by_1'=y\\ \end{cases}∴{ 2ax1′​+2by2′​=x 2ax2′​+2by1′​=y​
    有解的条件是(2a,2b)x\small (2a,2b)\mid x(2a,2b)∣x,(2a,2b)y\small (2a,2b)\mid y(2a,2b)∣y
    情况二x1y10\small x_1\equiv y_1\equiv 0x1​≡y1​≡0,y2x21\small y_2\equiv x_2\equiv 1y2​≡x2​≡1
    { ax1+by2=x ax2+by1=y\small \therefore \begin{cases} \ ax_1+by_2=x\\ \ ax_2+by_1=y\\ \end{cases}∴{ ax1​+by2​=x ax2​+by1​=y​
    将同余0\small 00的项提出2\small 22
    { 2ax1+by2=x ax2+2by1=y\small \therefore \begin{cases} \ 2ax_1'+by_2=x\\ \ ax_2+2by_1'=y\\ \end{cases}∴{ 2ax1′​+by2​=x ax2​+2by1′​=y​
    { 2ax1+b(y2+1)=x+b a(x2+1)+2by1=y+a\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​
    { 2ax1+2by2=x+b 2ax2+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​
    有解的条件是(2a,2b)(x+b)\small (2a,2b)\mid (x+b)(2a,2b)∣(x+b),(2a,2b)(y+a)\small (2a,2b)\mid (y+a)(2a,2b)∣(y+a)
    同理
    情况三:有解的条件是(2a,2b)(x+a)\small (2a,2b)\mid (x+a)(2a,2b)∣(x+a),(2a,2b)(y+b)\small (2a,2b)\mid (y+b)(2a,2b)∣(y+b)
    情况四:有解的条件是(2a,2b)(x+a+b)\small (2a,2b)\mid (x+a+b)(2a,2b)∣(x+a+b),(2a,2b)(y+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
/*
 
 
 
*/
上一篇:ISO Latin-1字符集


下一篇:剑指41.和为S的连续正数序列