177 GFact

[•domino]

Aici puteţi discuta despre problema GFact.

[•pauldb]

Pot considera ca B "intra" in int64 (long long)?

[•silviug]

Este destul de usor de observat ca B <= P * Q, deoarece (P * Q) ! se divide cu siguranta la P^Q, iar P * Q nu depaseste long long.

Silviu

[•cos_min]

imi puteti da niste teste k tot 5pcte iau pe pr plz

[andreit1]

2000000000 30000       1080015
123456 30000                         19260422
111111111 29999                    10009676333

Atat am obtinut eu cu un program de 100 de puncte. Sper sa fie bune.

[•alexthero]

Salut

Iau 90 de puncte la problema asta. Primesc "Wrong Answer" pe testele 13 si 19. Am facut descompunerea in factori primi a numarului A^B si am calculat pentru fiecare factor rezultatul, pastrand maximul. Imi puteti da unul dintre testele astea sa vad care e gresala? Mersi

Later Edit: Am gasit problema si am luat 100. Ms

[•domino]

Dupa cum s-a mai precizat (scrie si in regulamentul forum-ului) nu se dau testele folosite pentru evaluare.

[•gogu]

Pentru ca multi oameni tot timpu' cer teste sau pun unele pe forum si cer raspunsurile pentru ele, cred ca la fiecare problema ar trebui pus pe forum un test mai mare.
Nu din cele oficiale, doar unul destul de mare, cat sa se poata depana programul. Daca se poate chiar aproape de testele maxime.
Are cineva ceva impotriva daca se face asa?
Eu de exemplu am acasa facute cateva generatoare la unele probleme rezolvate de mine si pot sa pun teste daca vrea cineva.

[•Florian]

Eu nu pricep de ce iau TLE pe 4 teste...exista cazuri particulare pt testele 12, 13, 18, 19? Nu pot lua mai mult de 80. Am facut si cu cautare binara [k in articol] si dupa o idee de a mea. Am incercat sa verific programul de mii de ori  . L-am scris din nou de vreo 2 ori  Poate cineva sa ma ajute? Multumesc anticipat!

[•wefgef]

Poate ca iti intra in ciclu infinit pe unele cazuri particulare.

[•Florian]

Problema asta ma dispera! Am luat toate punctajele posibile mai mici ca 85...intr-adevar...imi intra in ciclu infinit! Am totusi cateva nelamuriri:

1. Fie k un numar prim prin care se imparte p, iar r puterea la care apare k in descomp lui p. Nu prea sunt de accord cu articoloul care atribuie cautarii binare intervalul [ 1 ; r*q*k ] , pentru ca, in ciuda faptului k acest lucru pare logik si e si demonstrat in articol, cand fac cautarea pe interv [1 ; MAXLONG] iau 80 [din cauza a 4 tle-uri, si NU WA) , iar daca o fac k in articol mai pic vreo 2 teste. Ma puteti dumeri?
2. Cam cat de mare e long long-ul?
3. Cam pe unde ar putea sursa mea sa pice? Am facut ceva in genu`:
k=2;
cat timp (p!=1)
  {
    r=0;
    cat timp ( p%k==0 ) { r++; p/=k;}
    daca (r!=0) aplic cautare binara [folosind undeva r*q ];
    k++;  //k este factorul prim
  }
Deci aici e problema cu tle nu cu WA. Nu prea pot sa-mi dau seama unde gresesc... ce cazuri "particulare" exista? Unde poate sa-mi intre in ciclu infinit? Sunt 100% sigur ca nu e de la cautare binara!

[•silviug]

Inainte de a contrazice solutiile din articole (cred eu corecte in acest caz), a da vina pe compilator ("cat de mare e long long?") si pe loop-uri infinite ar trebui sa fii mai atent cand codezi.

Prima fraza din solutie spune asa: "Primul pas in rezolvarea problemei il reprezinta factorizarea numarului P. Acest lucru se poate realiza intr-o complexitate O(√P)".

Dupa cum imi pare mie tu faci descompunerea in factori primi in O(P). Pentru P prim si foarte mare acest lucru va duce la TLE (in fapt cazuri din astea pici tu). 

Daca nu stii cum se face descompunerea in O(sqrt(P)) mai intreaba pe forum.

Spor la treaba si mai calm pe viitor  ,

Silviu

[•Florian]

Deci...nu a spus nimeni ca nu sunt calm! In plus, nu am contrazis articolul, ci doar mi-am exprimat nelamuririle! Faza cu long long era doar o curiozitate, si nimic mai mult. Totusi, dupa cum am facut eu nu prea cred k e o(P), insa nici nu sunt convins ca e o(sqrt(P)). Nu cred k stiu cum se face factorizarea unui numar natural n in complexitate o(sqrt(n))? Poate cineva sa ma ajute? Doar ideea...

[•stef2n]

Orice numar P nu va avea 2 divizori primi mai mari ca sqrt(P). In caz contrar, inmultindu-i, ne da un numar mai mare ca P si ajungem la contradictie. Asadar, e suficient sa verificam si sa il impartim pe P la toti divizorii primi pana la sqrt(P) inclusiv, iar daca numarul ramane mai mare ca 1, e clar ca a ramas inca un factor prim la puterea 1.

[•silviug]

Totusi, dupa cum am facut eu nu prea cred k e o(P), insa nici nu sunt convins ca e o(sqrt(P)).

Repet: pentru P prim k-ul tau merge pana la P pentru ca nu gasesti niciun divizor mai mic decat el. Dati un exemplu simplu (de exemplu 13 1) si urmareste ce face programul.

Pentru ca sa faci O(sqrt(P)) opresti while-ul cand k*k > P. Daca P-ul este diferit de 1 trebuie sa-l pui si pe el in descompunere ca e numar prim. Ia de exemplu 26 si descompune-l (ar trebui sa te opresti cand k e 4 pentru ca 4 * 4 > 13).

Silviu

[•Florian]

Aha! In sfarsit cred k am inteles! Deci inmultesc impart p-ul la k atata timp cat k*k < <= p (silviug: ce faci pentru 25 de exemplu?), iar la sfarsit daca p!=1 asta inseamna ca p e numar prim [ma refer la p-ul ramas dupa impartiri ]. Intr-adevar! Cred k asta e problema! Va multumesc mult de ajutor! 


LE: Ei bine, am reusit sa fac de 100! Cu toate acestea am pus [ folosind notatia mea] o cautare binara pe intervalul [1,k*r*q] si luam 95 [cu WA pe testu 1], iar kand am pus [1, 2*k*r*q] am luat 100! [pt mine k reprezinta factorul prim care apare in descomp lu` p, r este puterea la care apare k, iar q are semnificatia din enunt]. Nu prea imi dau seama ce nu am inteles din articol...Va multumesc de ajutor! 

[•Robytzza]

pentru 550 1 raspunsul este 42? 

imi da si mie cineva nishte tete mai mici (<30000) ca nushtiu unde gresesc:(

Editat de moderator: Nu mai posta de doua ori consecutiv

[•Florian]

gfact.in

Cod:

550 1
10 13
100 100
123 437
20000 12345

gfact.out

Cod:

11
55
805
17507
197530

Cu sursa de 100. Sper sa nu fi bushit nik.

[•Robytzza]

ms de teste.Pe al doilea test mie nu imi da 55 ca,la 55 eu am 50 de 2 si  13 de 5 unde  imi mai apare un 2 in plus

[•DjSefu]

Imi poate spune cineva de ce imi da la 4,12 si 13 WA? M-am verificat cu testele voastre si imi da bine

[•Florian]

Pai..din moment ce iei atatea wa-uri, cred ca busesti ceva major. Vezi, poate nu faci cautarea binara pe un interval suficient de mare, sau poate gresesti la descompunerea in factori primi. Da`ti mai multe exemple, pana knd gasesti un test pe care nu da bine... 

[•Teodor94]

Iau 90 puncte cu Wrong pe testele 18,19.
Am descompus in factori primi A^B,am cautat primul numar care are toti exponentii numerelor prime din A^B mai mari sau egali cu exponentii descompunerii lui A^B.
la testul
111111111 29999   raspunsul este -2147483648 si cu long long...
anyone help?

[•vladtarniceru]

Fisierul de iesire va contine numarul natural B cu propietatea din enunt.

O mica greseala ..

[•dutzul]

hmm uitati ce afiseaza urmatorul program
#include <fstream>
using namespace std;
ifstream f("inm.in");
ofstream g("inm.out");
unsigned long long DE;
int main()
{
  DE=20000000*30000;
  g<<DE<<'\n';


  f.close();
  g.close();
    return 0;
}
afiseaza o valoare uriasa care nici decum nu coincide cu rezultatul oare dc?? si imi da la warning "integer overflow in expresion"

[•mathboy]

Incearca sa faci asa:

Cod:

DE = (unsigned long long)20000000*30000

De ce? Pentru ca initial inmultirea are loc intre 2 int-uri iar rezultatul va fi tot unul int. Convertind primul numar la tipul de date dorit inmultirea se va efectua si ea pe unsigned long long (cel cu mai multi biti).