[boj 1750] 서로소의 개수

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

1750번: 서로소의 개수

바텀업  2차원 디피로 풀 수 있는 문제이다.

주어진 수열을 처리하기 쉽게 정렬해준뒤

 

(이때, 중복을 생각하지 않아도 된다고 생각하면 안된다 수열 S = {2,2,3},이라고할때, {2,3}이 0번째 인덱스의 2와 1번째 인덱스의 2를 사용하는 2가지 경우가 나올 수 있기 때문이다.  (같은 수더라도 고른 위치에 따라 경우가 다르다))

 

2차원 테이블 dp[i][j]  =   i번째 인덱스까지 보고있을 때,  최대공약수가 j인 것의 총 개수

 

<점화식>

v = 수의 리스트

1)

dp[i][v[i]]=1; 

for (int j = 1; j <= v[i]; j++)dp[i][j] += dp[i - 1][j];

 

i번쨰 인덱스까지보았을때의 최대공약수가 j인것은, i -1번째 인덱스까지 보았을 때 최대공약수가 j인 것을

포함한다. 따라서 모두 돌면서 더해준다.

2)

for (int j = 1; j <= v[i]; j++)dp[i][gcd(v[i], j)] = (dp[i][gcd(v[i], j)] + dp[i - 1][j]) % MOD;

 

바텀업 방식이므로, dp[i-1][j].. i - 1번쨰 인덱스까지 봤을 때 최대공약수가 j인 것들은 전부 업데이트 되어있다.

이때,이미 있는 것에 현재 보고 있는 새로운 원소인 v[i]를 추가 했을 때 갱신되는 것을 반영해야 된다.

 

 

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 10000003;
typedef pair<int, int> pi;
ll dp[101][100001];
ll ans;
int gcd(int a, int b) {
    if (a % b==0)return b;
    return gcd(b, a % b);
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int>v(n);
    for (int& i : v)cin >> i;
    sort(v.begin(), v.end());
    for (int i = 0; i < n; i++) {
        dp[i][v[i]] = 1;
        if (i == 0)continue;
        for (int j = 1; j <= v[i]; j++)dp[i][j] += dp[i - 1][j];
        for (int j = 1; j <= v[i]; j++)dp[i][gcd(v[i], j)] = (dp[i][gcd(v[i], j)] + dp[i - 1][j]) % MOD;
    }
    cout << dp[n - 1][1];
}