D. X-Magic Pair(辗转相除)

Problem - 1612D - Codeforces

 

给你一对整数（a,b）和一个整数x。

你可以用两种不同的方式改变这对整数。

设置（分配）a:=|a-b|。
设置（分配）b:=|a-b|。
其中|a-b|是a和b之间的绝对差值。
如果只用给定的操作就能得到a或b，那么这对(a,b)就被称为x-magic(即，如果经过一定数量的操作后a=x或b=x，这对(a,b)就是x-magic)。你可以应用任何次数的操作（甚至是零）。

你的任务是找出这对(a,b)是否是x-magic。

你必须回答t个独立的测试案例。

输入
输入的第一行包含一个整数t（1≤t≤104）--测试案例的数量。接下来的t行描述测试用例。

测试用例的唯一一行包含三个整数a，b和x（1≤a，b，x≤1018）。

输出
对于第i个测试案例，如果相应的一对（a,b）是x-magic，则打印YES，否则打印NO。

例子
输入复制
8
6 9 3
15 38 7
18 8 8
30 30 30
40 50 90
24 28 20
365 216 52
537037812705867558 338887693834423551 3199921013340
输出拷贝
是
是的
是
是
没有
是
是
是

题解:
有一个结论,如果一个永远是一个大的数减一个小的数,得到的数都会出现

但是一直相减时间复杂度太大,所以我们选择相除,

如果此时a%b == x%b 并且a >= x说明,x一定可以出现

否则a = a%b,直到a或b等于0

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define int long long
int a,b,x;
void solve()
{
	cin >> a >> b >>x;
	while(a&&b)
	{
		if(a < b)
		swap(a,b);
		if(a%b == x%b &&a >= x)
		{
			cout<<"YES\n";
			return;
		}
		a = a%b;
	} 
	cout<<"NO\n";
}
signed main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}
 
//1 10 11
 
//001
//010
//011
//100