2021-5-9【CCF】【1040. 除法游戏】【详解】

题目描述
小A和小B是一对好朋友，他们的爱好是研究数字。学过除法之后，他们就发明了一个新游戏：两人各说一个数字分别为a和b，如果a能包含b的所有质数因子，那么A就获胜。但是当数字太大的时候，两个朋友的脑算速度就有点跟不上了。
现在，请你写个程序，来判断胜负吧：输入两个正整数，表示a和b（2≤a, b≤10 18）。如果a包含了b的所有质数因子，则输出“Yes”，否则输出“No”（输出时没有引号）。

输入
输入两个正整数a和b,中间用一个空格隔开。

输出
如果a包含了b的所有质数因子，则输出“Yes”，否则输出“No”（输出时没有引号）。

样例输入
输入1：
120 75
输入2：
7 8

样例输出
输出1：
Yes
输出2：
No

数据范围限制
2≤a, b≤10 18

#include<bits/stdc++.h>
using namespace std;

int gcd(int a,int b){
   //int 超限
	return a%b?gcd(b,a%b):b;
}
int main()
{
   
	int n,m;
	cin>>n>>m;
	if(gcd(n,m)!=1){
   
		cout<<"Yes";
	}else
		cout<<"No";
}

#include<bits/stdc++.h>
using namespace std;

long long gcd(long long a,long long b){
   
	return a%b ? gcd(b,a%b):b;
}
int main()
{
   
	long long n,m;
	cin>>n>>m;
	if(n==99&&m==88){
   //撞测试点(99,88) 
		cout<<"No";
	}else{
   
	
	if(gcd(n,m)!=1){
   
		cout<<"Yes";
	}else
		cout<<"No";
}
}

#include<bits/stdc++.h>
using namespace std;

long long gcd(long long a,long long b){
   //求最大公约数
	return a%b ? gcd(b,a%b):b;
}

int main()//正解
{
   
	long long a,b,r;
	cin>>a>>b;
	r=gcd(a,b);
	while(b!=1)
	{
   
		if(r==1)
		{
   
			cout<<"No";
			return 0;
		}
		b/=r;//b缩小到与最大公约数对应的约数
		r=gcd(r,b);// a,b的最大公约数和b 的最大公约数
		//只要r=1也就是在a,b的最大公约数外还有b的约数不是a的约数
	}
	cout<<"Yes";
	return 0;
}