UOJ 48 题解

假设我们有两个原子，它们的核聚变特征值分别为 x 和 y。

首先，我们找出 x 的所有质因数。这可以通过试除法来实现。我们从 2 开始尝试将 x 进行分解，如果 x 能被 i 整除，则说明 i 是 x 的一个质因数。我们重复这个过程，直到 x 无法再被整除为止。

对于第二个原子的核聚变特征值 y，我们计算 x 和 y 的最大公约数 d = gcd(x, y)。最大公约数可以通过欧几里得算法来计算。

如果 d 等于 1，则说明 x 和 y 互质，即它们没有共同的质因数，无法进行核聚变反应，输出 -1。

如果 d 大于 1，说明 x 和 y 存在一个共同的质因数，即它们可以进行核聚变反应。我们需要找到这个共同的质因数中最大的一个，即次大公约数。这个次大公约数即为 x 的所有质因数中与 d 同时也是质因数的最大值。

最后，输出这个次大公约数作为核聚变反应的强度。

 C++ 20
#import "bits/stdc++.h"
#define endl '\n'
#define ll long long

using namespace std;

const int maxn = 200001;
const int mod = 10007;
const int inf = 0x3f3f3f3f;

ll a[maxn], p[maxn];
int n, Num;
char CH[12];

inline void P(int x)
{
    Num = 0;
    if(!x) {
        cout << 0 << endl;
        return;
    }
    while(x > 0) { CH[++Num] = x % 10, x /= 10; }
    while(Num) { putchar(CH[Num--] + 48); }
    cout << endl;
    return ; 
}

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    { scanf("%lld", &a[i]); }
    ll tot = 0;
    ll x = a[0];
    for(ll i = 2; i <= sqrt(x); i ++) {
        if(x % i == 0) {
            while(x % i == 0) { x /= i; }
            p[tot++] = i;
        }
    }
    for(int i = 0; i < n; i ++) {
        ll d = gcd(a[0], a[i]);
        int flag = 1;
        for(int j = 0; j < tot; j ++) {
            if(d % p[j] == 0) {
                printf("%lld ", d / p[j]);
                flag = 0;
                break;
            }
        }
        if(flag) {
            if(d != 1)
            { cout << 1 << ' '; }
            else
            { cout << -1 << ' '; }
        }
    }
    return 0;
}

chcrt0x的博客

博客

评论

发表评论