当前位置: 首页 > 工具软件 > Magic Copy > 使用案例 >

X-Magic Pair

刘建中
2023-12-01

You are given a pair of integers (a,b) and an integer x.

You can change the pair in two different ways:

  • set (assign) a:=|a−b|;
  • set (assign) b:=|a−b|,

where |a−b| is the absolute difference between a and b.

The pair (a,b) is called x-magic if x is obtainable either as a or as b using only the given operations (i.e. the pair (a,b) is x-magic if a=x or b=x after some number of operations applied). You can apply the operations any number of times (even zero).

Your task is to find out if the pair (a,b) is x-magic or not.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1≤t≤104) — the number of test cases. The next t lines describe test cases.

The only line of the test case contains three integers a, b and x (1≤a,b,x≤1018).

Output

For the i-th test case, print YES if the corresponding pair (a,b) is x-magic and NO otherwise.

Example

input

Copy

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

output

Copy

YES
YES
YES
YES
NO
YES
YES
YES

思路:这题的减法是取绝对值的,变换之后永远是正数,那么,我们可以一直将大的数减去小的数,这样便能跳过取绝对值的过程,取绝对值的过程就是大的减小的,所以用大的减小的便能模拟出所有的情况。所以只要x出现在a,b中能说明能够变成。但cf总会拐两个弯(对于人家不是,只是对于我这种垃圾而言)出现边界时(如 1,99999999)时,必会超时,那么就要优化了,我们举一个不太大的例子来模拟一下就会发现,一直减小的的过程中是一直重复的,如:(30,7)与(9,7)是一样的而且在下 一次的变化中,变成(2,7)更改了之后大小发生变化,在30变到9的过程中是一直减7的,且都比7的倍数多2,其实30与9是等价的,(30-9)%7==0,这样便能模拟出逐渐减7的过程,节省了很多步骤,大的数除余会得到更小的数,刚好得到变化之后较小的值,所以要在变化之前模拟减法的过程。

结论:除余能很好地优化减法的过程,不仅是(a-x)%b,而且还有大的数变成小的数的过程

除余1:除余的最大余数(除它本身)最大只能到 一半(奇数时,一半是向下取整)或一半减一(偶数时)即(n-1)/2。

除余2:当我们要求的某个数是由乘法与加法混合组成的,可以使用除余得出要加的数,用除法得出剩下的乘数。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

int main()
{
	int t;
	cin>>t;
	while(t--)
    {
        ll a,b,x;
        cin>>a>>b>>x;
        bool ok=true;
        while(a&&b)
        {
            if(a<b) swap(a,b);
            if(a==x||b==x)
            {
                ok=false;
                cout<<"YES"<<endl;
                break;
            }
            else if(x<=a&&(a-x)%b==0)
            {
                ok=false;
                cout<<"YES"<<endl;
                break;
            }
            a=a%b;
        }
        if(ok) cout<<"NO"<<endl;
    }
	return 0;
}

 类似资料: