CCF NOI1040. 除法遊戲 (C++)

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

C++代碼

#include <iostream>
#include <cmath>
#include <cassert>
#include <ctime>

using namespace std;

long long gcd(long long m, long long n)
{
    return (n == 0) ? m : gcd(n, m % n);
}

bool checkPrime(long long n)
{
    if ((n <= 1) || (n!=2 && n%2==0)) 
    {
        return false;
    }

    long long root = (long long)sqrt((long double)n);

    for(long long i=3; i<=root; i+=2)
    {
        if (n%i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    long long a, b;
    bool b_has_a_allPrimeFactors;

    cin >> a >> b;

    if (a%b == 0)  // b is one divisor/factor of a
    {
        b_has_a_allPrimeFactors = true;
    }
    else
    {
        if (1 == gcd(a, b))   // a and b are co-prime
        {
            b_has_a_allPrimeFactors = false;
        }
        else
        {
            b_has_a_allPrimeFactors = true;

            for(long long i=2; i<=(long long)sqrt((long double)b); i++)
            {
                if (b%i == 0 && true == checkPrime(i) && a%i != 0)
                {
                    b_has_a_allPrimeFactors = false;
                    break;
                }
                else if (b%i == 0 && true == checkPrime(b/i) && (a%(b/i) != 0))
                {
                    b_has_a_allPrimeFactors = false;
                    break;
                }
            }
        }
    }
    
    if (true == b_has_a_allPrimeFactors)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

           

另一種求解方法

#include <iostream>

using namespace std;

class DivisionGame
{
private:
    long long gcd(long long m, long long n);

public:
    bool win(long long a, long long b);
};

long long DivisionGame::gcd(long long m, long long n)
{
    return (n == 0) ? m : gcd(n, m % n);
}

bool DivisionGame::win(long long a, long long b)
{
    long long c = gcd(a, b);
 
    b = b / c;
    if(c % b == 0)
    {
        return true;
    }
    return false; 
}

int main()
{
    long long a, b;
 
    cin >> a >> b;

    DivisionGame noi1040;
    
    if (true == noi1040.win(a, b))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}