Conteggio dei divisori

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
zip92
Messaggi: 6
Iscritto il: 19 nov 2009, 15:27

Conteggio dei divisori

Messaggio da zip92 » 07 feb 2010, 19:41

Salve. In questi giorni sto provando a risolvere alcuni problemi presenti nel correttore online del sito delle olimpiadi.

Uno di questi non l'ho proprio capito

Conteggio dei divisori (contdivisori)
Descrizione del problema
Sia x un numero intero. Diremo che y è un divisore di x se 1 <= y <= x e il resto della divisione di x per y è
uguale a zero.
Si chiede di contare tutti i possibili divisori di un dato numero x.
Dati di input
Il file di input contiene un intero x (1 <= x <= 10^18). Tutti i divisori primi di x non superano 1000.
Dati di output
Deve contenere il risultato richiesto dal problema.

Qualcuno riesce ad illuminarmi? Non ho capito soprattutto quel "tuttti i divisori primi di x non superano 1000", come faccio a trovare tutti i divisori di x senza testare tutti i numeri da 1 a x?

kwehmucdee
Messaggi: 17
Iscritto il: 16 gen 2010, 19:38
Contatta:

Messaggio da kwehmucdee » 07 feb 2010, 21:50

Per esempio 24 ha 8 divisori: 1, 2, 3, 4, 6, 8, 12, 24.
Tra questi divisori alcuni sono primi: 2, 3.
In questo caso non ci sono divisori primi maggiori di 1000.

Comunque non c'è bisogno di controllare tutti i numeri da 1 a x (anche perché se x può essere 10^18 il tuo programma andrebbe ben oltre il limite di tempo).

Se ci pensi bene non c'è bisogno di andare oltre x/2: non c'è numero maggiore della metà che sia divisore di x (escluso x stesso ovviamente). Ma questo non migliora comunque la situazione: dovremmo comunque provare 5^18 possibili divisori

Pensandoci ancora meglio non c'è bisogno di andare oltre $ \sqrt {x} $: appena trovi un divisore y aggiungi anche x/y (che sarà maggiore di $ \sqrt {x} $ o, nel caso di un quadrato perfetto, potrebbe essere anche uguale, attento a gestire questo caso). Questo ci porta a dover analizzare 10^9 possibili divisori, un miliardo, un bel miglioramento ma che potrebbe non essere sufficiente.

Sapendo però che il numero di divisori è una funzione moltiplicativa è sufficiente fattorizzare il numero (e sapendo che i suoi divisori primi non superano 1000 non ci metti molto) e quindi moltiplicare il numero di divisori di tutti i suoi fattori primi (che è facile sapendo che il numero di divisori di un numero primo p, elevato alla n, è uguale a n+1).

Se vuoi vedere una soluzione, ho scritto questo:

Codice: Seleziona tutto

#include <fstream>
using namespace std;

unsigned long long int N;

int factors_exp[998];

int main()
{
	int num_factors = 1;
	ifstream fin("input.txt");
	fin >> N;
	fin.close();
	while (N % 2 == 0)
	{
		factors_exp[2]++;
		N = N / 2;
	}
	for (int i = 3; i < 998; i+=2)
	{
		while (N % i == 0)
		{
			factors_exp[i]++;
			N = N / i;
		}
	}
	
	for (int i = 2; i < 998; i++)
	{
		num_factors *= factors_exp[i] + 1;
	}
	ofstream fout("output.txt");
	fout << num_factors << endl;
	fout.close();
	
	return 0;
}
che calcola il numero di divisori di 920756754918000 in 27ms.

zip92
Messaggi: 6
Iscritto il: 19 nov 2009, 15:27

Messaggio da zip92 » 07 feb 2010, 22:43

Grazie infinite per la tua spiegazione e per il programma di esempio.

Ciao :D

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti