/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 525 点
問題文
AtCoder 島には N 種類のセミが生息しています。種類 i のセミ (1 \leq i \leq N) は A_i の倍数の年にのみ大量発生します。
1 年から Y 年までの Y 年間のうち、ちょうど M 種類のセミが大量発生する年が何回あるかを求めてください。
制約
- 1 \leq M \leq N \leq 20
- 1 \leq Y \leq 10^{18}
- 1 \leq A_i \leq 10^{18} (1 \leq i \leq N)
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M Y A_1 \cdots A_N
出力
答えを出力せよ。
入力例 1
3 2 16 4 2 3
出力例 1
4
1 年から 16 年までのうち、各種類のセミが大量発生するのは以下の年です。
- 種類 1 のセミは 4,8,12,16 年に大量発生する。
- 種類 2 のセミは 2,4,6,8,10,12,14,16 年に大量発生する。
- 種類 3 のセミは 3,6,9,12,15 年に大量発生する。
1 年から 16 年までのうち、ちょうど 2 種類のセミが大量発生するのは 4,6,8,16 年の 4 回です。
入力例 2
2 1 122333444422333 1429 73651
出力例 2
87266392324
答えが 32bit 整数に収まらないことがあります。
入力例 3
20 3 832725971730072237 19639596380058 49098990950145 32732660633430 114564312217005 68738587330203 45825724886802 252041486877411 180029633483865 108017780090319 72011853393546 468077047058049 297867211764213 212762294117295 127657376470377 85104917646918 723391799998803 612100753845141 389518661537817 278227615384155 166936569230493
出力例 3
24231
入力される値が 32bit 整数に収まらないことがあります。
Score : 525 points
Problem Statement
AtCoder Island has N species of cicadas. Cicadas of species i (1 \leq i \leq N) have mass outbreaks only in years that are multiples of A_i.
Among the Y years from year 1 to year Y, find how many years have mass outbreaks of exactly M species of cicadas.
Constraints
- 1 \leq M \leq N \leq 20
- 1 \leq Y \leq 10^{18}
- 1 \leq A_i \leq 10^{18} (1 \leq i \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M Y A_1 \cdots A_N
Output
Output the answer.
Sample Input 1
3 2 16 4 2 3
Sample Output 1
4
From years 1 to 16, each species of cicada has mass outbreaks in the following years:
- Species 1 cicadas have mass outbreaks in years 4,8,12,16.
- Species 2 cicadas have mass outbreaks in years 2,4,6,8,10,12,14,16.
- Species 3 cicadas have mass outbreaks in years 3,6,9,12,15.
From years 1 to 16, exactly two species of cicadas have mass outbreaks four times in years 4,6,8,16.
Sample Input 2
2 1 122333444422333 1429 73651
Sample Output 2
87266392324
The answer may not fit in a 32-bit integer.
Sample Input 3
20 3 832725971730072237 19639596380058 49098990950145 32732660633430 114564312217005 68738587330203 45825724886802 252041486877411 180029633483865 108017780090319 72011853393546 468077047058049 297867211764213 212762294117295 127657376470377 85104917646918 723391799998803 612100753845141 389518661537817 278227615384155 166936569230493
Sample Output 3
24231
Input values may not fit in a 32-bit integer.