동전
시간 제한2초메모리 제한256 MB
그가 y짜리 동전을 x짜리로 착각해 세었을 때, 세어진 합이 S이고 실제 지불한 합이 T가 되는 동전 단위 순서쌍 (x, y)의 개수를 센다.
문제
Ankh-Morpork은 활발한 교역이 이루어지는 거대한 도시다. 항구에는 아주 먼 나라에서 온 배들이 드나든다. 그래서 여러 나라의 동전이 많이 유통된다. 교역을 간편하게 하려고 각 동전에는 도시의 공식 통화인 Ankh-Morpork 달러에 대한 고정 환율이 있다. 이 환율을 동전의 액면가라고 부르자.
이런 다양성 때문에 노련한 시민도 가끔 동전을 혼동한다. 마법사 Rincewind도 최근에 새 모자 값으로 내야 할 S 달러 대신 T 달러를 냈다. 그가 이 사실을 알아차렸을 때 상인은 이미 자취를 감춘 뒤였다.
Rincewind는 자기가 어떤 동전을 다른 동전으로 착각했다고 본다. 예를 들어 두블론을 스털링으로 착각한 식이다. 그가 스털링을 세고 있다고 생각할 때마다 실제로는 두블론을 낸 셈이고, 진짜 스털링은 하나도 내지 않았다. 예를 들어 Rincewind는 두블론 하나와 스털링 둘을 냈다고 생각했지만 실제로는 두블론 셋을 냈을 수 있다.
Rincewind는 첫 번째 동전을 두 번째 동전으로 착각해서 S 달러 대신 T 달러를 정확히 낼 수 있었던 동전 쌍이 몇 개인지 궁금하다.
예를 들어 액면가가 1달러, 2달러, 3달러인 동전이 유통되고 Rincewind가 9달러 대신 10달러를 냈다면, 액면가 2달러 동전을 액면가 1달러 동전으로 착각해서 2달러 동전 네 개와 1달러로 착각한 2달러 동전 하나를 내는 식으로 낼 수 있다. 또한 액면가 3달러 동전을 액면가 2달러 동전으로 착각해서 1달러 동전 일곱 개와 2달러로 착각한 3달러 동전 하나를 낼 수도 있다.
액면가가 2달러, 3달러, 4달러인 동전이 유통되고 Rincewind가 10달러 대신 11달러를 냈다면, 액면가 3달러 동전을 액면가 2달러 동전으로 착각해서 4달러 동전 두 개와 2달러로 착각한 3달러 동전 하나를 내는 식으로 낼 수 있다.
입력
첫째 줄에 세 정수 S, T, n이 주어진다 (1 ≤ S, T ≤ 10000; S ≠ T; 1 ≤ n ≤ 200). 각각 모자의 가격, Rincewind가 쓴 금액, 동전의 개수다.
다음 줄에 n개의 정수 a1, a2, ..., an이 주어진다. 이는 동전의 액면가다 (1 ≤ ai ≤ 10000). 두 동전의 액면가가 같은 경우는 없다.
출력
첫 번째 동전을 두 번째 동전으로 착각해서 Rincewind가 S 달러 대신 T 달러를 낼 수 있었던 동전 쌍의 개수를 출력한다.