WHCSRL 技术网

CCF在线OJ除法游戏(1040)详解

1040 除法游戏

题目描述

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

输入格式

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

输出格式

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

样例 1 输入

120 75

样例 1 输出

Yes

样例 2 输入

7 8

样例 2 输出

No

数据范围

2 ≤ a, b ≤ 1018

算法 1 暴力模拟(90分)

#include<bits/stdc++.h> 
using namespace std;
typedef long long LL;
int main() {
	LL a, b;
	cin >> a >> b;
	for(LL i = 2; i * i <= b; i++) {
		if(b %% i != 0) continue;

		if(a %% i != 0) {
			cout << "No";
			return 0;
		}
		while(b %% i == 0) {
			b /= i;
		}

	}
	if(a %% b == 0) cout << "Yes";
	else cout << "No";
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

算法 2 最大公约数(递归版本)

#include<bits/stdc++.h> //  a = 120 = 3 * 5 * 8,    b = 75 = 3 * 5 * 5
using namespace std;    //  只需要判断 b 除共同部分外的 5 是否在共同部分(gcd) 3 * 5 里
typedef long long LL;
bool dg(LL a, LL b) { // 3*5   5*5*5
	LL gcd = b, t, sh;
	while(a %% gcd != 0) {
		t = a %% gcd;
		a = gcd;
		gcd = t;
	}
	sh = b / gcd;  // sh表示 b 除掉最大公约数 gcd 以外的因子
	if(gcd %% sh == 0) return true;
	else if (gcd == 1 && b != 1) {
		return false;
	} else {
		return dg(gcd, sh);
	}
}
int main() {
	LL a, b;
	cin >> a >> b;
	if(dg(a, b)) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

算法 3 最大公约数(循环版本)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
	LL a, b, flag = 0;
	cin >> a >> b;
	while( true ) { // 3*5   5*5*5
		LL gcd = b, t, sh;
		while(a %% gcd != 0) {
			t = a %% gcd;
			a = gcd;
			gcd = t;
		}
		sh = b / gcd;
		if(gcd %% sh == 0) {
			flag = 1;
			break;
		} else if (gcd == 1 && b != 1) {
			flag = 0;
			break;
		} else {
			a = gcd;
			b = sh;
		}
	}
	if(flag) cout << "Yes";
	else cout << "No";
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
推荐阅读