[백준 22357] 경품 추첨 (UCPC 2021 예선) (Platinum IV)

https://www.acmicpc.net/problem/22357

22357번: 경품 추첨

 

출력할 수 있는 수의 제한이 500만 이하로 매우 작다는 것에 주목, 번호들을 최대한 구겨넣어서 생성하는 방법을 생각해 보자. 예컨대 K = 2, N = 5라면 다음과 같이 2~26까지의 수를 모두 생성하는 것이 가능하다.

	1	6	11	16	21
1	2	7	12	17	22
2	3	8	13	18	23
3	4	9	14	19	24
4	5	10	15	20	25
5	6	11	16	21	26

따라서 등차수열을 이용하면 수를 구겨넣어서 생성하다는 데 유리하다는 사실을 짐작할 수 있다. 그렇다면 그 등차수열의 공차(d)는 몇이 되어야 할까? 이에 대한 답을 얻기 위해서는 먼저 N에 대한 제약을 풀고 무한 등차수열이라고 가정한 뒤, 두 무한 등차수열로부터 생성되는 공들 중 처음으로 겹치는 공의 번호가 몇 번인지 살펴보자. 간단한 관찰을 통해, 그 답은 2 + lcm(d1, d2)라는 결과를 얻는다. 그러므로 그냥 d1, d2를 2000보다 큰 소수로 정하면 된다.

#include<bits/stdc++.h>

std::array primes = {
        2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081,
        2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141,
        2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239
};

int main() {
    int K, N; std::cin >> K >> N;

    for (int i = 0; i < K; ++i) {
        int p = primes[i];
        for (int j = 0; j < N; ++j) {
            std::cout << 1 + j * p << ' ';
        } std::cout << '\n';
    }
}