XOJ 3455：除法游戏

矫情吗；* 2022-02-15 06:53 182阅读 0赞

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

--------------------

###### Input Data ######

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

###### Output Data ######

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

--------------------

##### Input / Output Sample #####

120 75

Yes

--------------------

##### 代码实现： #####

#include <cstdio>
    long long gcd(long long m, long long n)   //辗转相除法求最大公因数
    { 
        if(m%n == 0) return n;
        return gcd(n, m%n);
    }
    int main()
    { 
        long long a, b, c;            //10^18大于2^32,要使用long long
        scanf("%lld%lld", &a, &b);
        c = gcd(a, b);
        while(c > 1)        //一个数可分解为a = 1*.*.*.*.,找到a，b之间的公因子
        { 
            b = b / c;
            c = gcd(a, b);
        }
        if(b > 1)          //得到一个a不含b的因子(非1)，使c为1退出上述循环，b>1
            printf("No\n");
        else               //得到最后b为1，b与a的公因子为1退出上述循环，即都包含
            printf("Yes\n");  
    
        return 0;
    }

--------------------

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关除法游戏

题目描述：小A和小B是一对好朋友，他们的爱好是研究数字。学过除法之后，他们就发明了一个新游戏：两人各说一个数字分别为a和b，如果a能包含b的所有质数因子，那么A就获胜。但

谁借莪１个温暖的怀抱￠/ 2022年12月30日 07:48/ 0 赞/ 196 阅读

相关 Python | 除法

１．除法除 / 整除 // 求余 % 商和余数的元组 divmod a = 9 b = 2 r1 = a/b

Dear 丶/ 2022年10月05日 13:54/ 0 赞/ 151 阅读

相关大数除法

参考代码： <span style="font-family:KaiTi_GB2312;font-size:18px;">//除数为int值，结果

落日映苍穹つ/ 2022年08月05日 02:59/ 0 赞/ 206 阅读

相关计算机除法

计算机除法前不久看了《C++反汇编与逆向分析技术揭秘》，看到除法的介绍部分，里面有1道题 8 % -3 = ?; \-8 % -3 = ?; \-8 % 3 =

╰+攻爆jí腚メ/ 2022年04月24日 09:10/ 0 赞/ 176 阅读

相关 XOJ 2569：生日相同

> 在一个有180人的大班级中，存在两个人生日相同的概率非常大，现给出每个学生的学号，出生月日。试找出所有生日相同的学生。 -------------------- In

以你之姓@/ 2022年02月16日 08:15/ 0 赞/ 195 阅读

相关 XOJ 3455：除法游戏

> 小A和小B是一对好朋友，他们的爱好是研究数字。学过除法之后，他们就发明了一个新游戏：两人各说一个数字分别为a和b，如果a能包含b的所有质数因子，那么A就获胜。但是当数字太大

矫情吗；*/ 2022年02月15日 06:53/ 0 赞/ 183 阅读

相关 XOJ 1569：校门外的树

> 某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，

本是古典何须时尚/ 2022年02月13日 10:59/ 0 赞/ 174 阅读

相关 XOJ 2808：整数去重

> 给定含有n个整数的序列，要求对这个序列进行去重操作。所谓去重，是指对这个序列中每个重复出现的数，只保留该数第一次出现的位置，删除其余位置。 ---------------

小灰灰/ 2022年02月13日 10:57/ 0 赞/ 153 阅读

相关 P3455 [POI2007]ZAP-Queries

[传送门][Link 1] 首先对于询问 $x,a,b$ 答案就是 $f\[x\]=\\sum\_\{i=1\}^\{a\}\\sum\_\{j=1\}^\{b\}\[gcd

╰半橙微兮°/ 2021年12月17日 02:49/ 0 赞/ 155 阅读

相关 CCF 除法

一、试题问题描述　　小葱喜欢除法，所以他给了你N个数a1, a2, ⋯, aN，并且希望你执行M次操作，每次操作可能有以下两种：　　给你三个数l, r, v

曾经终败给现在/ 2021年09月14日 09:34/ 0 赞/ 400 阅读