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?
Conteggio dei divisori
-
- Messaggi: 17
- Iscritto il: 16 gen 2010, 19:38
- Contatta:
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:
che calcola il numero di divisori di 920756754918000 in 27ms.
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;
}