/* -*- coding: utf-8 -*- * * 1463.cc: No.1463 Hungry Kanten - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 18; const int MAX_A = 1000; const int MAX_P = MAX_N * MAX_A; /* typedef */ typedef pair pii; typedef vector vpii; typedef vector vvpii; /* global variables */ bool primes[MAX_P + 1]; int pnums[MAX_P], as[MAX_N]; vpii apds[MAX_N]; /* subroutines */ int gen_primes(int maxp, int pnums[]) { memset(primes, true, sizeof(primes)); primes[0] = primes[1] = false; int p, pn = 0; for (p = 2; p * p <= maxp; p++) if (primes[p]) { pnums[pn++] = p; for (int q = p * p; q <= maxp; q += p) primes[q] = false; } for (; p <= maxp; p++) if (primes[p]) pnums[pn++] = p; return pn; } bool prime_decomp(int n, int pn, int pnums[], vpii& pds) { pds.clear(); for (int i = 0; i < pn; i++) { int pi = pnums[i]; if (pi * pi > n) { if (n > 1) pds.push_back(pii(n, 1)); return true; } if (n % pi == 0) { int fi = 0; while (n % pi == 0) n /= pi, fi++; pds.push_back(pii(pi, fi)); } } return false; } int bnum(int n) { int c = 0; for (; n > 0; n >>= 1) c += (n & 1); return c; } void mulpd(vpii &a, vpii &b, vpii &c) { c.clear(); int an = a.size(), bn = b.size(); int ai = 0, bi = 0; while (ai < an && bi < bn) { if (a[ai].first < b[bi].first) c.push_back(a[ai++]); else if (a[ai].first > b[bi].first) c.push_back(b[bi++]); else { c.push_back(pii(a[ai].first, a[ai].second + b[bi].second)); ai++, bi++; } } while (ai < an) c.push_back(a[ai++]); while (bi < bn) c.push_back(b[bi++]); } /* main */ int main() { int pn = gen_primes(MAX_P, pnums); //printf("pn=%d\n", pn); int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) { scanf("%d", as + i); prime_decomp(as[i], pn, pnums, apds[i]); } int nbits = 1 << n; vvpii ans; for (int bits = 0; bits < nbits; bits++) { if (bnum(bits) < k) continue; int sum = 0; vpii ppd; for (int i = 0, bi = 1; i < n; i++, bi <<= 1) if (bits & bi) { sum += as[i]; if (ppd.empty()) ppd = apds[i]; else { vpii ppd0; mulpd(ppd, apds[i], ppd0); swap(ppd, ppd0); } } vpii spd; prime_decomp(sum, pn, pnums, spd); ans.push_back(spd); ans.push_back(ppd); } sort(ans.begin(), ans.end()); ans.erase(unique(ans.begin(), ans.end()), ans.end()); printf("%d\n", (int)ans.size()); return 0; }