CCF NOI1040 除法游戏

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

小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

提示

问题分析

这个问题的关键是因子。

两个数的最大公约数里包含了所有的共有的因子。

知道最大公约数后，进一步对b进行计算就知道了。

程序说明

（略）

要点详解

最大公约数是数论中重要的概念，通常用欧几里德算法实现。
通常需要根据数值范围选用合适的类型。

参考链接：（略）。

100分通过的C语言程序：

#include <stdio.h>

// 最大公约数
long long gcd(long long m, long long n)
{
    return (n == 0) ? m : gcd(n, m % n);
}

int main(void)
{
    long long a, b, c;

    scanf("%lld%lld", &a, &b);

    c = gcd(a, b);

    b = b / c;
    if(c % b == 0)
        printf("Yes
");
    else
        printf("No
");

    return 0;
}