L33t H4xX0R, 96/100

Aiuto
1

Salve a tutti,
ho provato a risolvere il problema L33t H4xX0R con un algoritmo lineare.
In poche parole mi salvo la frequenza dei valori inferiori a sqrt(K) in un vettore di dimensioni sqrt(K) e mi calcolo il numero di coppie come la somma di freq[K/A_i] per ogni valore A_i maggiore di sqrt(K).
Il tempo dovrebbe essere di O(N) mentre di spazio occupa O(sqrt(K)+N) che soddisfano entrambi il requisiti.
Il problema è che il testcase 004 mi dà output errato e non so quale sia il problema.
Il mio codice è questo:

int N;
long long K;
in >> N >> K;

int radk = sqrt(K);

vector<int> freq(radk+1,0);
deque<long long> coda;

for (int i=0; i<N; i++)
{
	long long temp;
	in >> temp;
	if (temp > radk)
		coda.push_back(temp);
	else
		freq[temp]++;
}

long long coppie = 0;
for (int i=0; i<coda.size(); i++)
{
	if (K%coda[i] == 0)
		coppie += freq[K/coda[i]];
	coppie %= mod;
}

long long temp = freq[radk];
coppie += temp*(temp-1)/2;

out << coppie%mod;

Grazie a chiunque risponderà.

2

Siccome ho lo stesso problema, mi sai dire se hai risolto ed hai trovato l’errore?

3

Alla fine avevo risolto, stai attento a quando K non è un quadrato

2 Mi Piace