Problema Perfecte#1960 de pe Pbinfo

Problema este pentru clasa a IX-a.

Enuntul este urmatorul:

Un număr natural nenul se numește perfect dacă este egal cu suma divizorilor săi naturali strict mai mici decât el.
Exemplu: 28 este număr perfect pentru că 28 = 1 + 2 + 4 + 7 + 14.

Cerința
Se dă un șir de n numere naturale. Pentru fiecare element din șir se va afișa valoarea 1 dacă acesta este perfect sau 0 în caz contrar.

Date de intrare
Programul citește de la tastatură numărul n și apoi n numere naturale.

Date de ieșire
Programul va afișa pe ecran șirul de valori 1 și 0 separate prin câte un spațiu, conform cerinței.

Restricții și precizări
0 < n < 1000
numerele citite vor fi mai mici decât 10^19.

Nu inteleg ce este gresit la sursa mea, ia doar 5 puncte si aparent nu este destul de eficienta..?

#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
	 unsigned long long suma = 1, x;
	 cin >> x;
	 for (int j = 2; j * j <= x; ++j) {
		 if (x % j == 0) {
			 suma += j;
			 if (j * j < x) {
				 suma = suma + x / j;
			 }
		 }
	 }
	 if (suma == x)
		 cout << 1 << ' ';
	 else
		 cout << 0 << ' ';
}
return 0;
}

Tin sa mentionez ca am gasit rezolvarile de 100 puncte, dar nu au absolut niciun sens, nu sunt explicate deloc si nu inteleg nimic. Prefer sa primesc niste hint-uri de pe aici de ce nu functioneaza programul si sa iau 50 de puncte decat sa iau 100 pe copy-paste. Totusi, daca puteti sa explicati dvs. ce fac sursele de 100 puncte voi lasa link-urile:

https://brainly.ro/tema/6567720

https://tutoriale-pe...zolvari-pbinfo/

Edited by bencxikyoungG, 26 December 2020 - 16:50.

Numerele perfecte din intervalul [0, 10¹⁹] sunt destul de putine (8 mai exact ... le gasesti in array-ul din al doilea link).
Stiind care sunt, poti face o cautare pentru fiecare element citit sa vezi daca se regaseste si el pe acolo.

Ce e in primul link e un jeg fara comentarii de ce/cum face ce face acolo pare ca-si construieste si el numerele perfecte intr-un array si cauta la fel pentru fiecare numar citit daca se afla sau nu in acel array.

Edited by sftpdt, 26 December 2020 - 17:36.

Chiar si asa,
ai nevoie de o functie care verifica numarul, generand divizorii, si o functie care face suma de numere,
celei de pe urma nu o sa ii  pese ca sunt divizor, numere sa fie

Edited by MarianG, 26 December 2020 - 18:21.

Prima solutie pare a-si precalcula numerele perfecte, desi nu sunt convins ca principial e corecta. Mai precis nu cred ca s-ar putea extinde la numere oricat de mari (presupunand ca are la dispozitie precizie/ memorie/ timp nelimitate). Foloseste o anumita forma particulara pe care o au numerele prime pare: 2^p−1(2^p − 1) cu p prim si 2^p-1 prim (sursa: <https://en.wikipedia.../Perfect_number>). Lista de acolo cred ca sunt cele mai mici valori p pentru care 2^p-1 sunt prime. Aici deja triseaza pentru ca nu calculeaza/enumera numere prime si verifica daca 2^p-1 prim ci ia direct rezultate din alta parte. Apoi nu se stie daca exista numere perfecte impare iar asa zisa solutie pur si simplu ignora posibilitatea ca asemenea numere sa existe. O fi ok pentru numere suficient de mici, dar dupa mine aceasta nu face rezolvarea 100% corecta.

In a doua ‘solutie’ (cu ghilimelele de rigoare) triseaza direct si grosier. Si-a luat de undeva toate rezultatele posibile profitand de faptul ca sunt putine (in intervalul de valori dat), apoi nu verifica decat daca numarul primit e in lista.

Edited by sags, 26 December 2020 - 18:30.

if (x % j == 0) {
						 suma += j;
						 if (j * j < x) {
								 suma = suma + x / j;
						 }
				 }

if ( numar % divizor == 0)
{
suma += divizor;
if (divizor*divizor < numar ) suma+= (numar/divizor)
}

Ideea este ca gasesc cate 2 divizori la fiecare impartire

Edited by MarianG, 26 December 2020 - 18:32.

Pentru un timp de rulare mai mic suma divizorilor se poate calcula din descompunerea in factori primi, vezi aici <https://planetmath.o...orsumofdivisors>. Poti enumera numerele prime, si pentru cele care divid numarul dat determini puterea si faci imediat calculul care depinde de acel prim. (Nu e nevoie sa pastrezi divizorii primi explicit.) Valoarea puterii curente folosita pentru a calculata puterea maxima e tocmai buna pentru acest calcul. Poti precalcula o tabela de numere prime folosind de exemplu Ciurul lui Eratostene.

Edited by sags, 26 December 2020 - 18:38.

Mda, din cate am inteles, solutia mea ar fi trebuit de fapt sa primeasca 100 de puncte si singurul mod realist prin care pot sa o iau(tinand cont ca problema este pentru clasa a IX-a, este sa iau direct rezultatele gata facute, care sunt puse intr-un vector pe cand problema nu ar trebui sa foloseasca vectori. Ideea cu formulele si cu Ciurul lui Eratostene e foarte grea de implementat, si niciunde la indicatii nu se precizeaza de asta.

Dat fiind intervalul de valori admise de problema, o eroare in codul tau care poate face ca programelul sa cicleze la infinit este ca j e declarat de tip int. j * j poate depasi (la un calcul cu precizie infinita) intervalul de numere reprezentabile pe int caz in care rezultatul e trunchiat la cat incape (pe 32 biti cu semn) si nu convertit automat la un tip cu mai muilti biti (unsigned long long in acest caz) Daca x e suficient de mare comparatia j * j <= x va fi totdeauna adevarata si intri intr-un ciclu infinit.

Oricum, dupa mine trebuie sa schimbi abordarea/algoritmul din temelii. Tu practic poti avea acolo un ciclu de la 2 la 10¹⁹ si nu vad cum ai putea sa te incadrezi in 0,1 secunde in aceste conditii. Ar fi unele optimizari pa care le poti face, ma gandesc continui ciclul doar daca j * j < x (fara ‘egal’) si sa testezi separat, dupa ciclu, j * j == x. Dar chiar si asa, 10¹⁹ este ingrozitor de mare…

LE: Si mai e ceva, care ar putea explica raspunsul gresit cu timp de rulare neglijabil: ce rezultat da programelul tau in cazul numarului 1?

Edited by sags, 27 December 2020 - 19:49.

E o problema foarte grea pentru a putea fi rezolvata prin cautare pe computer.
Iar o solutie matematica completa, wikipedia zice ca nu exista.
Desigur, poti sa pui secventa lor gasita de altii pe net, dar nu mi se pare o solutie corecta.