163. 수학은 너무 쉬워
1.Python
2. C++
#include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; //
int gcdCount[80000]; //gcd가 될 것 같은 횟수
int answer1, answer2; //가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
/*
// debug
for (int i = 0 ; i < n ; i++) {
printf("[%d] : ", a[i]);
for (int j = 0 ; j < prime.size() ; j++) {
if (count[i][j] != 0) {
printf("prime %d %d, ", prime[j], count[i][j]);
}
}
printf("\n");
}
*/
for (int i = 0; i < prime.size(); i++){
gcdCount[i] = totalCount[i] / n;
//n개에다가 분배
}
answer1 = 1;
for(int i = 0; i < prime.size();i++){
for (int j = 0; j < gcdCount[i]; j++){
answer1 *= prime[i];
}
//각 숫자들에 대해서 GCD가 되기 위해서 소수가 얼마나 부족한지 확인
for (int j = 0; j < n; j++){
if(count[j][i] < gcdCount[i]){
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}
Author And Source
이 문제에 관하여(163. 수학은 너무 쉬워), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@corone_hi/163.-수학은-너무-쉬워저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)