CF1612D X-Magic Pair

题意：

给一个数对 \((a,b)\) ，每次可以进行操作 \((a,b) \to (|a-b|,b)\) 或 \((a,b) \to (a,∣a−b∣)\)，问最后能否令 \(a=x\) 或 \(b=x\)

分析：

题目中出现了状态之间的转换，我们不妨装模做样地来一个状态分析（尽管这是个数论题）。

首先，令 \(a\) 远远大于 \(b\)，可以得到：

\((a,b)\to(a-b,b)\) 或 \((a,b)\to(a,a-b)\)

\[(a,a-b) \to (b,a-b) 或(a,b)
\]

观察这个柿子的转移结果，不难发现，他跟之前所得到的是等价的。

\[(a-b,b)\to(a-b-b,b)或(a-b,a-b-b)
\]

同理，在这个式子里面，只有转移结果左边的那个柿子才能继续向外转移。

综上，可以发现，在本题中，数对总是会这样转移：\((a,b)\to (a-b-b-...,b)\)。自然，当前一项小于后一项时，交换并继续处理，这就很像欧几里得算法了！

AC代码：

#include<bits/stdc++.h>

#define int long long

using namespace std;

int a,b,c;

void Swap(int &a,int &b){

	int c = a;

	a = b;

	b = c;

}

bool check(int a,int b,int c){

	if(a < b){

		swap(a,b);//交换

	}

	if(a == c || b == c)return 1;//假如两个数中有任意一个数等于给出的数，那么目标已经达到，返回true

	if(!a || !b)return 0;

	if(c > a)return 0;//如果当前处理到的最大值已经小于目标值，那么就不可能达到，返回false

	if(a % b == c % b)return 1;

	return check(a % b,b,c);

}

int t;

signed main(){

	cin >> t;

	while(t--){

		cin >> a >> b >> c;

		bool flag = check(a,b,c);

		if(flag)cout << "YES\n";

		else cout << "NO\n";

	}

}

巴特西

CF1612D X-Magic Pair

题意：

分析：

AC代码：

最新文章

热门文章