当前位置:首页 > 数学 > 正文
CCF1040除法游戏
3203+

题目大意:输入两个比较大的正整数a和b,求b的质因子是否都是a的因子。

题目描述

小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

解题思路

有大于1的最大公约数即有共同质因子,b一直除以a和b的最大公约数,直到最大公约数为1。如果最后b是1,则质因子都被a包含,否则不是。

程序实现

About

坚决不Copy代码!

本文标签:,,,,

CCF1040除法游戏:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!