백준 1750 c++

#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 10000003

using namespace std;

void input_data(int* N, vector<int>& S, int* max_value) {
    int i, s;
    cin >> *N;
    for (i = 0; i < *N; i++) {
        cin >> s;
        S.push_back(s);
        *max_value = max(s, *max_value);
    }
}

int gcd(int A, int B) {
    if (B == 0) {
        return A;
    }
    else {
        return gcd(B, A % B);
    }
}

int find_answer(int N, vector<int>& S, int max_value) {
    int answer = 0;
    int i, j;
    int current, new_gcd;
    vector<vector<int>> DP(N + 1, vector<int>(max_value + 1, 0));
    DP[0][0] = 1; // 초기값 설정: 아무것도 선택하지 않은 경우

    for (i = 1; i <= N; i++) {
        current = S[i - 1];
        cout << "current = " << current << " : ";
        for (j = 0; j <= max_value; j++) {
            DP[i][j] = DP[i - 1][j];// 이전 단계의 값을 그대로 가져옴
            new_gcd = gcd(current, j);// 새로운 GCD를 계산
            DP[i][new_gcd] = (DP[i][new_gcd] + DP[i - 1][j]) % MOD;
        }

        // 현재 값 자체를 GCD로 추가
        DP[i][current] = (DP[i][current] + 1) % MOD;

        for (j = 0; j <= max_value; j++) {
            cout << DP[i][j] << " ";
        }
        cout << "\n";
    }

    // GCD가 1인 모든 경우의 수를 결과에 합산
    answer = DP[N][1];
    return answer;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, max_value = 0;
    vector<int> S;

    input_data(&N, S, &max_value);
    cout << find_answer(N, S, max_value) << "\n";

    return 0;
}