[1750] 서로소의 개수

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

naive하게 생각하면 포함-배제의 원리를 생각하기 쉬우나 조금 생각해보면 TLE가 떨어질거라는 확신이 드는 문제이다. DP를 이용해 N개의 원소중 1~i번째 숫자들을 후보로 하여 최대공약수가 j인 갯수를 d[i][j]라고 놓으면 생각보다 쉽게 점화식을 세울 수 있다.

#include <stdio.h>

#define MAX 10000003

#define LL long long

int num[101];

__inline int min(int a, int b) {

    return a < b ? a : b;

}

void q_sort(int low, int hi) {

    int i = low;

    int j = hi;

    int pivot = num[(i + j) >> 1];

    while (i <= j)

    {

        while (num[i] < pivot) i++;

        while (num[j] > pivot)j--;

        if (i <= j)

        {

            int tmp = num[i];

            num[i] = num[j];

            num[j] = tmp;

            i++;

            j--;

        }

    }

    if (i < hi) q_sort(i, hi);

    if (low < j) q_sort(low, j);

}

int gcd(int a, int b) {

    if (b > a) {

        int tmp = b;

        b = a;

        a = tmp;

    }

    if (a%b == 0) return b;

    else return gcd(a%b, b);

}

int main() {

    int N;

    scanf("%d", &N);

    for (int i = 1; i <= N; i++) scanf("%d", num + i);

    q_sort(1, N);

    int d[101][100001] = { 0 };

    for (int i = 1; i <= N; i++)

    {

        d[i][num[i]] = 1;

        for (int j = 1; j <= num[i]; j++) //*

        {

            d[i][j] += d[i - 1][j];

            d[i][j] %= MAX;

            int n_num = gcd(j, num[i]);

            d[i][n_num] += d[i - 1][j];

            d[i][n_num] %= MAX;

        }

    }

    printf("%d\n", d[N][1]);

}




//*인 for문에서 1부터 전체를 돌지말고, 이전 idx까지의 공약수들만 검색하면 된다고

생각했는데 accepted가 안떨어져서 무식하게 1부터 다 돌렸다..