X = x0, Y = y0
  print X, Y
  for i = 1 to n - 1
    X = (A * X + B)  MOD M
    Y = (C * Y + D) MOD M

    [문제 풀이]

  삼각형을 만들 수 있는 경우를 세어 봅시다. n개의 좌표가 입력으로 주어지는 경우, 이 중에서 3개를 순서없이 고르는 경우가 되니, nC₃이 되겠지요. Small Dataset의 경우에는 n이 겨우 100밖에 되지 않으므로 모든 경우를 고려해서 풀어도 답을 구할 수 있습니다. 이 경우는 어렵지 않으니 소스코드는 생략하도록 할게요 :)

  그러면 이제 Large Dataset을 풀어봅시다. Large Dataset은 n이 10만이기 때문에 위의 방법으로는 구할수가 없지요.

  (1, 2), (3, 5)를 두 점으로 잡고 나머지 한 점의 좌표를 (x, y)라고 가정할 때 이 세 점으로 중심이 "정수 좌표"가 되는 조건을 찾아보도록 합시다. 우선 x좌표가 정수가 되어야 하므로, (1 + 3 + x) / 3 = k (k는 임의의 정수) -> 1 + 3 + x = 3k -> x = 3k - 4 꼴이 됩니다. 마찬가지로 y좌표의 조건을 구햅보면 y = 3m - 7꼴이 되지요. 즉, x와 y 모두 3으로 나누었을 때 나머지가 2인 모든 점에 대하여 중심이 정수좌표인 삼각형을 만족시키게 됩니다. 좀 더 확장해서 생각하면 어차피 우리가 만들고자 하는 것은 3으로 나누었을때의 나머지만 가지고 계산해도 상관이 없으므로, 모든 좌표를 3으로 나눈 나머지로 표현해도 답이 같게 나옴을 알 수 있습니다.  

  그러면 총 9가지의 상태가 나오게 됩니다. 이제 이 점들을 가지고 만들 수 있는 모든 삼각형의 갯수를 세어주면 Large Dataset도 풀 수 있게 되는 것이지요. 자세한 것은 아래의 소스코드를 참조해주세요. 생각보다 어렵지 않으니까요 :)

    [문제 풀이]

  이 문제를 그래프로 변환해서 생각해 보도록 하겠습니다. 각각의 수를 Vertex로 두고, 임의의 두 수가 동시에 P 이상의 소수로 나누어 떨어진다면, 두 Vertex 사이를 잇는 Edge를 생성해 줍시다.

  그러면 이 문제는 몇개의 Disjoint Graph인지 구하는 문제로 변환이 가능합니다. Small Dataset은 n이 작기 때문에 adjacent matrix로 그래프를 표현해도 풀리지만, Large Dataset의 경우는 n이 꽤 크기 때문에 adjacent list로 그래프를 나타내야 하지요. :) 또한 3, 6, 9, 12의 경우에는 모두 3으로 나누어 떨어지기 때문에 3-6, 3-9, 3-12, 6-9, 6-12, 9-12 이렇게 여섯개의 Edge가 생성될 수 있지만, Disjoint Graph의 여부인지 구하는 것이 우리의 목표이기 때문에, 3-6, 3-9, 3-12의 정보만 가지고 있다고 하더라도 정해를 구할 수 있게 됩니다.

  아래의 제 소스 코드는 adjajcent list로 graph를 구성하여 graph의 수를 count하는 방식으로 구현되어 있습니다. 이 방법을 사용하지 않고,  Disjoint Set을 쓰는것도 하나의 솔루션이 될 수 있겠지요. :) Disjoint Set으로 짠 소스는 다른 분이 올려주실거라 믿고 B번의 풀이는 여기서 마치겠습니다. :-P

#include <vector> #include <cstdio> #include <algorithm> #include <queue> #include <iostream> using namespace std; int prime[1000001]; // 0 -> prime vector <vector <int> > graph; vector <int> check; void bfs(int num) {     queue<int> Q;     Q.push(num);     check[num] = 1;     while (!Q.empty()) {         int v = Q.front(); Q.pop();         for (int i = 0; i < graph[v].size(); ++i) {             if (check[graph[v][i]] == 0) {                 check[graph[v][i]] = 1;                 Q.push(graph[v][i]);             }         }     } } int main() {         int T;     long long A, B, P;     scanf("%d", &T);     // 소수는 에라토스테네스의 체를 사용하여 구합니다.     for (long long i = 2; i <= 1000000; ++i) {         if (prime[i] == 0) {             for (long long j = i * i; j <= 1000000; j += i)                 prime[j] = 1;         }     }     for (int cn = 1; cn <= T; ++cn) {         cin >> A >> B >> P;         graph.assign(B - A + 1, vector <int> ());         check.assign(B - A + 1, 0);         for (long long i = P; i <= B - A; ++i) {             if (prime[i - A]) continue;             int start = ((A + (i - 1)) / i) * i;             for (long long j = start + i; j <= B; j += i) {                 graph[start - A].push_back(j - A);                 graph[j - A].push_back(start - A);             }         }         int ret = 0;         for (long long i = A; i <= B; ++i) {             if (check[i - A] == 0) {                 ret++;                 bfs(i - A);             }         }         cout << "Case #" << cn << ": " << ret << endl;     } }

    [문제 풀이]

  Small DataSet부터 풀어 봅시다. 항상 첫번째 위치에는 1이 들어가 있겠지요. 그리고 한칸 건너뛰어 2가 들어가 있고, 두칸 건너뛰어 3이... 이런 식으로 채워져 있게 됩니다. 만약 세는 도중에 다른 숫자가 채워져 있다면 skip하고 count하는 방식으로 채워 나갈 수 있습니다.

  Small DataSet의 K가 5000이라고 하더라도, 단순히 채워나간다면 시간안에 답을 구하기 힘들 것입니다. 따라서 간단한 처리를 해 주어야 겠지요. 만약 현재 전체 카드가 200장, 남은 카드가 3장이고, 197칸 건너뛰어야 한다고 가정해 봅시다. 200장을 한 번 훑어 볼 때 마다 우리는 겨우 3칸 건너뛰는 연산을 할 것이며, 197번이나 무의미한 skip연산을 하게 되지요. 이러한 필요없는 연산을 줄이기 위해 "나머지 연산"을 사용합니다. 197번 건너뛰나 194번 건너뛰나 ... 2번 건너뛰나 결과는 같게 될 테니까요. 이 방법만 사용해 주더라도 시간 안에 원하는 답을 구할 수 있게 됩니다.

  하지만 Large DataSet은 위의 방법을 사용하더라도 한계에 부딪치게 됩니다. K가 너무 크거든요. Large DataSet을 풀기 위해 다른 방법으로 접근해 보도록 하지요. :0

  N = 5일때의 경우를 예로 들어 설명하도록 하겠습니다. 배열을 하나 잡고 이 배열을 unused라고 부르도록 하지요. 즉 아직 채워져 있지 않은 칸을 나타냅니다.

  unused : 1  1  1  1  1 --> 초기 상태입니다. 우선 우리는 첫번째 칸에 항상 1이 들어가는 것을 알지요. 이제 첫번째 칸의 값을 0으로 바꾸겠습니다.
  unused : 0  1  1  1  1 --> 첫번째 칸의 값이 0이 되었습니다. 그러면 이제 우리는 현재 위치에서 한칸 점프하고, 그 다음칸을 선택해야 겠지요. 현재 위치는 첫번째이므로 한칸 (두번째 위치)을 점프하고 다음 1이 있는 위치는 세번째 위치가 됩니다. 여기에 2가 들어가겠네요.
  unused : 0  1  0  1  1 --> 세번째 칸의 값도 0이 되었습니다. 이번엔 두 칸 점프합니다. 네 번째, 다섯 번째 위치를 점프하고 다음에 나오는 1은 두 번째 위치네요. 이제 여기에는 3이 들어갈 것입니다.
  unused : 0  0  0  1  1 --> 두 번째 위치에서 세 칸 점프할 차례입니다. 그러면 네번째, 다섯번째, 네번째를 점프하고 다섯번째 칸에 4가 들어갑니다. 반복하면 네 번째 위치에 5가 들어가죠. 즉 "1 3 2 5 4"라는 값이 완성됩니다.

  위에서 사용한 연산을 정리하면 크게 두 가지 연산이 있습니다.
  1) 1 지우기 ... ①
  2) 현재 위치에서 k번 점프한 위치 구하기
  하지만 현재 위치에서 k번 점프한 위치 구하기는 "현재 위치보다 앞에 몇개의 1이 있는지 구하기.. ②" 연산과 "i번째 1찾기.. ③" 연산으로 구할 수 있습니다. 현재 위치를 알고 i번째 위치를 찾을 수 있다면 (2)를 구할 수 있으니까요.

  Binary Indexed Tree (정식 명칭인지는 가물가물) 를 사용하여 풀어보도록 하겠습니다. 아래쪽의 사각형은 Leaf Node를 의미하고, 가운데에 있는 원은 Non-Leaf Node로, 각 값은 자기 하위 노드들의 합으로 구성되어 있습니다. 원과 사각형 밖에 있는 값은 Tree Index입니다. (편의상 1-based Tree로 두었습니다.) N = 5일때의 트리를 나타내면 아래와 같습니다. Leaf Node는 위에서 설명했던 unused Array로 생각하시면 이해하기 쉬울 겁니다.




 여기에서 이제 ①을 적용해 봅시다. 1은 항상 첫번째 unused array를 0으로 만들게 되지요. 이러면 8번 index를 0으로 바꿔줍니다. 이 때 8번 node의 ancestor node인 4, 2, 1번의 값은 모두 1씩 감소하게 되지요. 이 다음 상태는 아래의 트리와 같이 됩니다.



  이제 현재 위치 (8번 노드, unused의 첫번째 위치) 앞에 몇 개의 1이 있는지 찾아보는 ③번 과정을 수행해 봅시다. 사실 이건 별로 의미가 없지요 (0개니까요.) 그럼 다른 예를 들어 세번째 위치 (10번 노드) 앞에 몇 개의 1이 있는지 찾아봅시다.

 우리는 8,9,10번 노드의 합을 구하고 싶습니다. 하지만 이 것들을 일일이 더해준다면 O(N)만큼의 시간이 걸리게 되지요. 따라서 이렇게 트리로 나타낸 이유는 이 연산을 좀 더 빠르게 하고 싶기 때문입니다. 위의 경우만 보더라도, 8과 9의 합은 4번 노드에 저장이 되어 있지요. 즉 8,9,10번 노드의 합 = 4,10번 노드의 합이 되므로 좀 더 빠르게 계산할 수 있게 됩니다. 현재 위치를 k라고 하면 처음부터 k-1번째까지 몇 개의 1이 있는지 찾아보면 되는 것이지요.

  마지막으로 ②번 과정입니다. 두번째 트리에서 앞에서 세 번째 1을 찾는다는 요청이 들어왔을때의 처리 과정을 예를 들어 살펴보겠습니다. 이 과정은 루트에서부터 출발하는데요. 루트의 값이 4이므로, 루트 밑에 4개의 1이 존재한다는 뜻이 되겠습니다. 여기서 왼쪽 child의 값은 3, 오른쪽 child의 값은 1이지요. 우리가 찾고자 하는 3번째 값은 루트보다 왼쪽 노드에 있다는 것을 알 수 있습니다. 왼쪽 child의 값이 3이라는 것은 왼쪽에 1이 3개가 있다는 뜻이니까요.

  그럼 왼쪽으로 가서 (2번 인덱스) 살펴보면 왼쪽 child (4번) 값은 1, 오른쪽 child(5번) 값은 2임을 알 수 있습니다. 이번엔 오른쪽으로 가야겠지요. 오른쪽으로 이동하는 경우는 왼쪽에 있는 1을 빼 줍니다. 2번 인덱스를 기준으로 왼쪽 child 부분에 1이 1개 있으므로, 오른쪽 child에서 두번째 1을 찾으면 되기 때문이지요. 이 과정을 recursive하게 반복하면 11번 Node에 이르게 됩니다.

  위의 ①, ②, ③ 연산 모두 O(lg N)의 연산만에 해결할 수 있습니다. 이러한 과정을 N번 반복하면 모든 인덱스를 채울 수 있으므로 케이스마다 O(N lg N) 번의 연산을 통하여 답을 구할수가 있는 것이지요.

  아래의 소스코드에 주석은 없지만 설명과 매치시켜가면서 읽으신다면 이해하는 데 도움이 될 것입니다 :) 좋은 하루 되세요.