최대공약수가 1인 선택의 개수
시간 제한2초메모리 제한128 MB
최대 50개의 정수 중 공집합이 아닌 부분집합을 골라 최대공약수가 1이 되는 경우의 수를 10,000,003으로 나눈 나머지로 구합니다.
문제
수열 S가 주어진다. S에서 원소를 하나 이상 선택했을 때, 선택한 원소들의 최대공약수가 1이 되는 선택 방법의 수를 구하라.
같은 값이 여러 번 나오더라도 입력에서 위치가 다르면 서로 다른 원소로 취급한다.
입력
첫째 줄에 수열의 크기 N이 주어진다.
둘째 줄부터 N개의 줄에 수열의 원소 S_i가 하나씩 주어진다. 같은 수가 여러 번 나올 수 있다.
- 1 <= N <= 50
- 1 <= S_i <= 100,000
출력
조건을 만족하는 선택 방법의 수를 10,000,003으로 나눈 나머지를 출력한다.
힌트
모든 비어 있지 않은 선택을 고려하되, 각 선택의 최대공약수가 1인 경우만 센다.