PDA

Visualizza la versione completa : [C++] Conteggio Divisori


darth fener
07-02-2010, 10:16
Ho realizzato un programma per calcolare tutti i divisori di un numero solo che con gli n che sono circa 10^12 non funziona(va troppo lento).

Testo del problema


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


Mia soluzione inefficiente


#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
inline int operator % (vector<int>v, unsigned long long k) {
unsigned long temp = 0;
while (v.size() != 0) {
while (temp < k && v.size() != 0) {
temp = temp * 10 + v[0];
v.erase(v.begin());
}
temp = temp % k;
}
return temp;
}

int main() {
ifstream in;
ofstream out;
vector<int>v1;
register unsigned divisore;
in.open("input.txt");
if (in.is_open()) {
int temp = in.get();
while (temp >= '0' && temp <= '9') {
v1.push_back(temp - '0');
temp = in.get();
}
int cont = 0;
int primi = 0;
for (divisore = 1; divisore <= 100000; divisore++) {
if (v1 % divisore == 0)
cont++;
}
out.open("output.txt");
out << cont;
out.close();
in.close();
}
return 0;
}
}


Praticamente il problema che non s fino a quale numero k devo controllare che k sia divisore di x. Nel problema mi dice che tutti i divisori primi di x non superano 1000, ma non ho capito cosa vuol dire

c_junior
07-02-2010, 16:21
normale che pi vai in alto con i numeri pi lenta vado...ci vuole un certo tempo di esecuzione!

darth fener
07-02-2010, 16:37
No. Ci deve essere una soluzione migliore che risolva il problema in meno di 2 sec per qualsiasi input minore di 10^18. Forse il problema sta in quel "Tutti i divisori primi di x non superano 1000" che non ho capito cosa significa...

Loading