# ZeroJudge - d775: NOIP2009 3.細胞分裂
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=d775
###### tags: `ZeroJudge` `數學` `質數`

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define SIZE 35000

int primes[SIZE], primeAmount, base, power, baseFactors[10], factorPowers[10], factors;
bool notPrime[SIZE] = { true, true };

void Initialize() {
	for (int i = 2; i < SIZE; ++i) {
		if (!notPrime[i])
			primes[primeAmount] = i, ++primeAmount;
		for (int j = 0; i * primes[j] < SIZE; ++j) {
			notPrime[i * primes[j]] = true;
			if (!(i % primes[j]))
				break;
		}
	}
}

void AnalyzeBase() {
	int buffer = sqrt(base);
	for (int i = 0; primes[i] <= buffer; ++i) {
		if (!(base % primes[i])) {
			do {
				++factorPowers[factors]; base /= primes[i];
			} while (!(base % primes[i]));
			factorPowers[factors] *= power;
			baseFactors[factors] = primes[i]; ++factors;
		}
	}
	if (base != 1) {
		factorPowers[factors] = power;
		baseFactors[factors] = base; ++factors;
	}
}

int main() {
    cin.sync_with_stdio(false), cin.tie(nullptr);
	int kinds, reproduce, minimumTime = (1 << 30), cellTime;
	bool have = false, valid;
	Initialize();
	cin >> kinds >> base >> power;
	if (base == 1) {
		while (kinds--)
			cin >> reproduce;
		cout << "0\n";
	}
	else {
		AnalyzeBase();
		while (kinds--) {
			cin >> reproduce; valid = true; cellTime = 0;
			for (int i = 0, power = 0; i < factors; ++i, power = 0) {
				if (reproduce % baseFactors[i]) {
					valid = false;
					break;
				}
				do {
					++power; reproduce /= baseFactors[i];
				} while (!(reproduce % baseFactors[i]));
				cellTime = max(cellTime, int(ceil(1.0 * factorPowers[i] / power)));
			}
			if (valid) {
				minimumTime = min(minimumTime, cellTime);
				have = true;
			}
		}
		if (!have)
			cout << "-1\n";
		else
			cout << minimumTime << '\n';
	}
}