[백준 11790] Primorial vs LCM [C]

백준 - 11790

---

풀이

1부터 N까지의 LCM을 N이하인 소수들의 곱들로 나누면 되는 문제다.

N	LCM	facter	result
1	1	1	1
2	2	2	1
3	6	2	1
4	12	2 * 3	2
5	60	2^2 * 3	2
6	60	2^2 * 3 * 5	2
7	420	2^2 * 3 * 5 * 7	2
8	840	2^3 * 3 * 5 * 7	4
9	2520	2^3 * 3^2 * 5 * 7	12
10	2520	2^3 * 3^2 * 5 * 7	12

1~N의 LCM을 구할 때, N이하인 소수들의 거듭제곱으로 구하고 이를, N이하의 소수들로 나누어야 하므로

차수가 2이상인 소수들의 곱이 답이 된다.

 

때문에, result는 N이하인 소수의 거듭제곱으로 구할 수 있다.

다음과 같은 표를 생각해보자.

mol	prime
4	2
8	2
9	3
16	2
25	5
27	3
32	7
49	2
64	3

N의 result는 N이하인 mol의 prime들의 곱으로 미리 계산할 수 있다.

---

소스코드

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define ll long long
#define cMAX 10000001
const ll MAX = 1e14;
const int MOD = 1e9+7;

typedef struct{
    ll mol, prime;
}Prime;
Prime p[670122];
bool cNum[cMAX];
int idx = 1, result[670122] = {1};

int compare(const void *a, const void *b){
    Prime *n1 = (Prime*)a, *n2 = (Prime*)b;
    if (n1->mol - n2->mol < 0) return -1;
    else if (n1->mol - n2->mol > 0) return 1;
    return 0;
}
void set(){
    for (ll i = 2; i < cMAX; i++)
        if (!cNum[i]){
            for (ll j = 2*i; j < cMAX; j += i)
                cNum[j] = true;
			
            ll temp = i;
            while (temp <= MAX/i){
                temp *= i;
                p[idx].mol = temp;
                p[idx++].prime = i;
            }
        }
    qsort(p, idx, sizeof(Prime), compare);

    for (int i = 1; i < idx; i++)
        result[i] = result[i-1]*p[i].prime %MOD;
}
int main(){
    set();
	
    int T;
    scanf("%d", &T);
    for (int i = 1; i <= T; i++){
        ll N;
        scanf("%lld", &N);
		
        int left = 0, right = idx - 1, j;
        while (left <= right){
            int mid = (left + right) / 2;
			
            if (p[mid].mol <= N){
                j = mid;
                left = mid + 1;
            } else right = mid - 1;	
        }
        printf("Case %d: %d\n", i, result[j]);
    }
}

---

출처 및 참고자료

11790번: Primorial vs LCM

[백준 11690] LCM(1, 2, ..., n) [C]