5WA?求助
查看原帖
5WA?求助
1132336
122Mll楼主2024/1/25 20:57

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define m(a,b) a>b?b:a

bool isprime(ll num) {
    if (num == 1 || num == 4)return 0;
    if (num == 2 || num == 3)return 1;
    ll temp = ll(sqrt(num));
    if (temp == sqrt(num)) {
        for (int i = 2; i <= temp; i++) {
            if (num % i == 0)return 0;
        }
        return 1;
    }
    else {
        for (int i = 2; i <= temp; i++) {
            if (num % i == 0)return 0;
        }
        return 1;
    }
}

int main() {
    vector<ll> a, b;
    ll numa, numb,lcm,gcd=1;
    cin >> numa >> numb;
    ll tempa = numa, tempb = numb;
    for (ll i = 2; i <= tempa;) {
        if (isprime(tempa)) {
            //cout << isprime(tempa);
            a.push_back(tempa);
           // cout << "01tempa:" << tempa << '\n';
            break;
        }
        if (tempa % i == 0) {
            tempa /= i;
            a.push_back(i);
            i = 2;
            //cout << "02tempa:" << tempa << '\n';
        }
        else i++;
    }
    for (ll i = 2; i <=tempb;) {
        if (isprime(tempb)) {
            //cout << isprime(tempb);
            b.push_back(tempb);
            //cout << "01tempb:" << tempb << '\n';
            break;
        }
        if (tempb % i == 0) {
            tempb /= i;
            b.push_back(i);
            i = 2;
            //cout << "02tempb:" << tempb << '\n';
        }
        else i++;
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    //cout << (find(a.begin(), a.end(), 3)!=a.end())<< (find(b.begin(), b.end(), 3)!=b.end());

    for (ll i = 2;i<=10000; i++) {
        if (find(a.begin(), a.end(), i) != a.end() && find(b.begin(), b.end(), i) != b.end()) {
            gcd = i;
            break;
        }
    }
    if (numa > numb) {
        if (numa % numb == 0)lcm = numa;
        else lcm = numa > numb ? b[0] * numa : a[0] * numb;
    }
    else {
        if (numb % numa == 0)lcm = numb;
        else lcm = numa > numb ? b[0] * numa : a[0] * numb;
    }
    
    std::cout<<gcd<<' ' << lcm;
}
2024/1/25 20:57
加载中...