[CSP-S模拟测试]:金(king)（高精度+模拟）

题目传送门（内部题36）

输入格式

第一行一个整数$T$，表示数据组数。
接下来$T$行，每行两个空格隔开的整数$n,m$。

输出格式

对于每组数据，输出一行$"Yes"$或$"No"$（不包括引号），表示对于这组数据，扔西瓜无穷多次后，能否保证每个玩具小人都扔过西瓜。

样例

样例输入：

10
16 2
45 76
674091 234962
28687659 81999918
216966660425134880 694698856141666063
7917958698896159119471256123588118261064432286766395711821720896686225354014397 3
746849 229640484701817039414316292795728961279644416746723977234945018225880862408045
948324971099475 6357310881479510637970061186310751903627811585469901935558116653181536335266604
513581062809439938725941485703231626402353296549797226542655513017359376988934 56049011113707442491563165140739607603866754001957435234277149221957579519773
1405005705796027467337069061 140500570577788434

样例输出：

No
Yes
Yes
No
Yes
Yes
Yes
No
Yes
No

数据范围与提示

第$1$个测试点，$n\leqslant 100,m\leqslant 100$。
第$2$个测试点，$n\leqslant {10}^6,m\leqslant {10}^6$。
第$3$个测试点，$n\leqslant {10}^{18},m\leqslant {10}^{18}$。
第$4$个测试点，$m\leqslant 3$。
第$5$个测试点，$m\leqslant 10$。
第$6$个测试点，$m\leqslant {10}^6$。
第$7$个测试点，$n\leqslant {10}^6$。
第$8$个测试点，$n\leqslant {10}^{15}$。
第$9,10$个测试点，无特殊限制。
对所有测试点，$T=10$。$n$和$m$为长度不超过$100$的十进制正整数。

题解

显然如果$gcd(n,m)=1$的话输出$Yes$，否则输出$No$。

但是数据范围也显然要求我们打高精度。

在此介绍一种求$GCD$的方法。

$\alpha .n\%2=0$且$m\%2=0$时，$gcd(n,m)=2*gcd(\frac{n}{2},\frac{m}{2})$
$\beta .n\%2=0$且$m\%2!=0$时，$gcd(n,m)=gcd(\frac{n}{2},m)$
$\gamma .n\%2!=0$且$m\%2=0$时，$gcd(n,m)=gcd(n,\frac{m}{2})$
$\delta .n\%2!=0$且$m\%2!=0$时，$gcd(n,m)=gcd(n,abs(n-m))$

用这种方法可以降低代码复杂度。

而且注意$\alpha$情况直接输出$Yes$即可。

时间复杂度：$\Theta(\log \max(n,m))$

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

char ch[110];

int A[110],B[110];

int flag[110];

void chuA()

{

	int jw=0;

	for(int i=A[0];i;i--)

	{

		jw*=10;

		jw+=A[i];

		flag[i]=jw/2;

		jw%=2;

	}

	int len=0;

	int top=A[0];

	memset(A,0,sizeof(A));

	for(int i=top;i;i--)

	{

		if(flag[i])len=max(len,i);

		A[i]=flag[i];

	}

	A[0]=len;

}

void chuB()

{

	int jw=0;

	for(int i=B[0];i;i--)

	{

		jw*=10;

		jw+=B[i];

		flag[i]=jw/2;

		jw%=2;

	}

	int len=0;

	int top=B[0];

	memset(B,0,sizeof(B));

	for(int i=top;i;i--)

	{

		if(flag[i])len=max(len,i);

		B[i]=flag[i];

	}

	B[0]=len;

}

void change()

{

	if(A[0]==B[0])

	{

		for(int i=A[0];i;i--)

		{

			if(A[i]<B[i]){swap(A,B);return;}

			if(A[i]>B[i])return;

		}

		return;

	}

	if(A[0]<B[0])swap(A,B);

	return;

}

void jian()

{

	int jw=0;

	for(int i=1;i<=A[0];i++)

		if(A[i]-jw-B[i]<0)

		{

			flag[i]=A[i]-jw+10-B[i];

			jw=1;

		}

		else

		{

			flag[i]=A[i]-jw-B[i];

			jw=0;

		}

	if(jw)flag[A[0]]=0;

	int len=0;

	int top=A[0];

	memset(A,0,sizeof(A));

	for(int i=top;i;i--)

	{

		if(flag[i])len=max(len,i);

		A[i]=flag[i];

	}

	A[0]=len;

}

int gcd()

{

	change();

	if((B[0]==1&&B[1]==1)||(A[0]==1&&A[1]==1))return 1;

	if(!B[0]){if(A[0]==1&&A[1]==1)return 1;return 0;}

	if(!(A[1]&1)&&!(B[1]&1))return 0;

	if(!(A[1]&1)&&(B[1]&1)){chuA();return gcd();}

	if((A[1]&1)&&!(B[1]&1)){chuB();return gcd();}

	if((A[1]&1)&&(B[1]&1)){jian();return gcd();}

}

int main()

{

	int T;scanf("%d",&T);

	while(T--)

	{

		scanf("%s",ch+1);

		A[0]=strlen(ch+1);

		for(int i=1;i<=A[0];i++)

			A[i]=ch[i]-'0';

		reverse(A+1,A+A[0]+1);

		scanf("%s",ch+1);

		B[0]=strlen(ch+1);

		for(int i=1;i<=B[0];i++)

			B[i]=ch[i]-'0';

		reverse(B+1,B+B[0]+1);

		if(!A[1]&&A[0]==1){puts("Yes");continue;}

		change();

		if(gcd())puts("Yes");

		else puts("No");

	}

	return 0;

}

rp++

巴特西