[KOITP] 최대공약수가 1이 되는 것

출    처 : http://koitp.org/problem/GCDISONE/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	656	144 (22%)	123

문제

어떤 수열 S가 주어진다. 수열 S에서 한 개 이상 원소를 선택했을 때, 선택한 수 혹은 수들의 최대공약수가 1이 되는 것의 개수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100)

두 번째 줄부터 N개의 줄에 걸쳐 수열의 각 원소 Si가 주어진다. 어떤 두 원소가 같을 수 있다. (1 ≤ Si ≤ 100,000)

출력

첫 번째 줄에 정답을 10,000,003으로 나눈 나머지를 출력한다.

힌트

예제 입력

3
2
4
3

예제 출력

3

예제 설명

주어진 수를 이용해서 선택하는 모든 방법을 나열하면 아래와 같다.

• {2} : 최대공약수는 2이다.
• {3} : 최대공약수는 3이다.
• {4} : 최대공약수는 4이다.
• {2, 3} : 최대공약수는 1이고, 답이 되는 경우 중 한 가지가 된다.
• {2, 4} : 최대공약수는 2이다.
• {3, 4} : 최대공약수는 1이고, 답이 되는 경우 중 한 가지가 된다.
• {2, 3, 4} : 최대공약수는 1이고, 답이 되는 경우 중 한 가지가 된다.

즉, 총 3가지의 경우가 존재한다.

< Comment >

 점화식이 깔끔하게 정리하기 어려웠기 때문에, 점화식을 알고도 해석하는데 조금 시간이 걸렸습니다. 기본적으로 총 3가지의 케이스를 계산합니다. 우선 DP 함수인 D의 경우 아래와 같이 정의합니다.

 D(i, j) = i 번째 index까지 범위 내에서 최대 공약수가 j 인 집합의 수.

 약간 모호하게 들릴 수도 있지만 1 ~ i 까지의 범위 내에서, 최대공약수가 j가 되게 부분집합을 만드는 방법의 수를 의미합니다.

 이를 기반으로 점화식을 세우게 되면, 위에서도 언급했듯이 3가지의 경우로 나눌 수 있습니다. i - 1 번째 까지에서 i 번째로 확장되면, i 번째 원소만 선택하는 집합이 있을 수 있습니다. 해당 경우에는 D(i, A[i]) 를 1 증가시켜주면 됩니다.

 그리고 이외에는 i번째 원소인 A[i] 를 포함하지 않고 부분집합을 만들어, j라는 최대공약수를 가지는 경우들인데, 해당 경우들은 이미 D(i - 1, j) 에서 계산해 두었으므로, 추가적인 계산은 필요없이, 바로 가져와서 더해주면 됩니다.

 마지막으로 A[i]를 포함한 부분집합을 만드는 경우인데, 해당 경우에는, 앞서 A[i]를 뽑지 않고, 부분집합을 만드는 경우에 그냥 A[i] 만 추가적으로 더해주면 그 경우가 바로 A[i]를 포함하는 부분집합의 수가 됩니다. 대신 A[i] 가 추가될 경우, 새로운 최대공약수 GCD가 나올수도 있으니, A[i] 의 값과 j 의 최대공약수를 다시 구해주고, 이를 i 번째까지 뽑을 수 있을 때, GCD( j, A[i] ) 에 기존의 D(i - 1, j) 값을 넣어주면 됩니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class One {
	
	public static int N = 0;
	
	public static int A[] = null;
	public static long dp[][] = null;
	
	public static long MOD = 10000003;

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		A = new int[N + 1];
		
		int max = 0;
		for (int i = 1 ; i <= N ; i++) {
			
			A[i] = Integer.parseInt(br.readLine());
			max = Math.max(max, A[i]);
		}
		
		dp = new long[N + 1][max + 1];
		
		for (int i = 1 ; i <= N ; i++) {
			
			dp[i][A[i]] = (dp[i][A[i]] + 1) % MOD;
			for (int j = 1 ; j <= max ; j++) {
				
				if (dp[i - 1][j] == 0) {
					continue;
				}
				
				dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
				int gcd = GCD(j, A[i]); 
				dp[i][gcd] = (dp[i][gcd] + dp[i - 1][j]) % MOD;
			}
		}
		
		bw.write("" + dp[N][1]);
		bw.flush();
		bw.close();
	}
	
	
	public static int GCD(int a, int b) {
		
		if (b == 0) return a;
		return GCD(b, a % b);
	}
}