글 읽기 - c++입니다. 한 번만 도와주시면 감사하겠습니다.

robin0903 3년 전 0

데이터를 다양하게 만들어 봤는데 반례를 못 찾고 있습니다ㅠㅠ

도와주시면 감사하겠습니다

#include <cstdio>
#include <cstdbool>
#include <vector>
using namespace std;

int cnt[40100];
bool prime[40100];
vector <int> v;
int s, flag = 0;
const int MAX = 40000;
long long int ans = 1;

void p() {
    prime[1] = false;
    for (int i = 2; i <= MAX; i++) prime[i] = true;

    for (int i = 2; i <= MAX; i++) {
        if(prime[i]) {
        v.push_back(i);
            for (int j = i; i * j <= MAX; j++) {
                prime[i*j] = false;
            }
        }
    }
    return;
}

void c(int num) {
    for (int i = 0; i < s && v[i] <= num; i++) {
        while(num % v[i] == 0) {
            num /= v[i];
            cnt[v[i]]++;
            if(num == 1) return;
        }
    }
}

void a(int num) {
    for (int i = 0; i < s && v[i] <= num; i++) {
        while(num % v[i] == 0) {
            num /= v[i];
            if(cnt[v[i]] > 0) {
                ans = ans * v[i];
                if(ans > 999999999) {
                    flag = 1;
                    ans = ans % 1000000000;
                }
                cnt[v[i]]--;
            }
            if(num == 1) return;
        }
    }
}

int main() {
    p();

    int n, m, num;
    scanf("%d", &n);

    s = v.size();
    for (int i = 1; i <= n; i++) {
        scanf("%d", &num);
        if(num < 0) num = -num;
        c(num);
    }

    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &num);
        if(num < 0) num = -num;
        a(num);
    }

    if(flag == 0) printf("%lld", ans);
    else printf("%09lld", ans);

    return 0;
}

slah007 3년 전 0

유클리드 호제법으로 GCD(최대공약수) 구하기를 찾아보세요 꼭 알아야 할 내용 중 하나입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++입니다. 한 번만 도와주시면 감사하겠습니다.

robin0903 3년 전 0

slah007 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말