Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: 048 Suma si numarul divizorilor  (Citit de 17624 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« : Februarie 27, 2010, 21:29:49 »

Aici puteţi discuta despre problema Suma si numarul divizorilor.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #1 : Februarie 28, 2010, 15:49:12 »

Poti sa faci suma divizorilor fara invers modular.
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #2 : Februarie 28, 2010, 18:07:39 »

Poti sa faci suma divizorilor fara invers modular.
Cred că merge făcută împărțirea direct, posibil să nu iasă din long long. La asta te refereai? Smile
Memorat
borsoszalan
Strain


Karma: 5
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #3 : Martie 09, 2010, 10:15:01 »

pndn+1-1=(pn-1)*(pndn+pndn-1+pndn-2+...+dn+1)
Aşadsar (pndn+1-1)/(pn-1)=pndn+pndn-1+pndn-2+...+dn+1 şi nu trebuie folosit inversul modular.
Memorat
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #4 : Martie 13, 2010, 10:32:25 »

Am luat 100 fara ciurul lui Eratostene. Poate ar trebui date niste teste mai "grele".
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #5 : Martie 13, 2010, 15:35:42 »

Am luat 100 fara ciurul lui Eratostene. Poate ar trebui date niste teste mai "grele".
Am observat că sunt soluții care iau 100 și fără ciur, dar având în vedere că ideea principală a acestei probleme este aceea de a învăța că suma și numărul divizorizorilor se pot calcula și altfel decât căutând prin toate numerele mai mici ca N, nu cred că se impune ca testele să fie mai puternice.

Totuși, dacă este nevoie voi schimba o parte din teste.
Memorat
DEYDEY2
Strain
*

Karma: 1
Deconectat Deconectat

Mesaje: 49



Vezi Profilul
« Răspunde #6 : Iunie 18, 2010, 14:58:20 »

ma poate ajuta si pe mine cineva va rog? nu inteleg ce gresesc aici
Cod:
#include<fstream>
using namespace std;
long long k,maxim;
bool fol[1000001];
void ciur()
{
long long  i,j;
for(i=1;i*i<=maxim;i++)fol[i]=1;
for(i=2;i*i<=maxim;i++)
if(fol[i])
for(j=i+i;j*i<=maxim;j+=i)
fol[j]=0;
}
int main()
{
ifstream f("ssnd.in");
ofstream g("ssnd.out");
long long n[11]={0},i=0,nr=0,l=0,p=0,nn=0,suma=0,put=0,j=0;
f>>nn;
for(i=1;i<=nn;i++)
{
f>>n[i];
if(maxim<n[i]) maxim=n[i];
}
ciur();
for(l=1;l<=nn;l++)
{
nr=1;
p=0;
suma=1;
for(i=2;i*i<=n[l];i++)
{
p=0;
if(n[l]%i==0 && fol[i]==1) 
{
while(n[l]%i==0)
{
n[l]=n[l]/i;
p++;
}
nr=nr*(p+1);
put=1;
for(j=1;j<=p+1;j++) put=put*i;  suma=suma*((put-1)/(i-1));
}
}
g<<nr<<' '<<suma<<'\n';
}
f.close();
g.close();
return 0;
}
« Ultima modificare: Iunie 18, 2010, 15:27:20 de către Andrei Grigorean » Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #7 : Iunie 18, 2010, 16:30:07 »

Incearca sa pui limitele mai mari odata. Si in rest nu stiu, ia testele si vezi de ce nu iti da corect .
Memorat
BitOne
Strain
*

Karma: -1
Deconectat Deconectat

Mesaje: 45



Vezi Profilul
« Răspunde #8 : Iunie 18, 2010, 17:20:52 »

n[l], dupa ce l-ai descompus in factori primi, poate fi mai mare ca 1, ai uitat cazul asta Smile
Memorat
DEYDEY2
Strain
*

Karma: 1
Deconectat Deconectat

Mesaje: 49



Vezi Profilul
« Răspunde #9 : Iunie 20, 2010, 08:33:17 »

 Brick wall Brick wall ](*,)tot 50 pct:( ms băieţii am schimbat alea dar nu face nik am 2 incorecte si trei kill
alea două incorecte din 10 nr nu calculează bn la două si nu inteleg dc:(SadSad

are cineva vre-o idee?Huh Annoyed  Eh? Eh?

corectie 2 incorecte si tre TLE

Nu posta succesiv pe acelasi subiect. Modifica mesajele anterioare!
« Ultima modificare: Iunie 20, 2010, 11:02:19 de către Paul-Dan Baltescu » Memorat
BitOne
Strain
*

Karma: -1
Deconectat Deconectat

Mesaje: 45



Vezi Profilul
« Răspunde #10 : Iunie 20, 2010, 11:48:54 »

Sursa ta nu este implementata de 100pct din cate vad.  Am vazut ca ai facut ciurul, dar pe tine nu te ajuta daca x este prim sau nu, ci te intereseaza care sunt numerele prime  <= maxn. Plus ai niste probleme cu aritmetica modulara :
(a+b)%Modulo <=> ( a%Modulo + b%Modulo )%Modulo.
(a*b)%Modulo <=> ( (a%Modulo) * (b%Modulo) )%Modulo.
Memorat
ionutz32
Strain


Karma: 16
Deconectat Deconectat

Mesaje: 18



Vezi Profilul
« Răspunde #11 : Iunie 29, 2010, 17:03:34 »

Nu inteleg de ce sursa oficiala se complica in cazul cand n ramane > 1 si mai calculeaza fractia din formula, pentru ca e clar ca noul factor prim (adica n) apare in N la puterea 1, deci suma divizorilor trebuie sa se mai inmulteasca doar cu n+1.

Sunt cazuri cand intr-un numar din fisierul de intrare apare un factor prim cu exponentul 1 si al carui patrat nu ar intra pe long long si conform formulei o sa se apeleze factorul la puterea a doua.

De exemplu programul nu o sa mearga daca in fisier e numarul 999999999989.

Ar trebui inlocuita partea asta

Cod:
if(n > 1)
{
nd *= 2;
sd *= ((1LL*n*n - 1) % MOD);
sd %= MOD;
sd *= pow(n-1, MOD-2);
sd %= MOD;
}

cu asta

Cod:
if(n > 1)
{
nd *= 2;
sd = (1LL*sd*(n + 1)) % MOD;
}
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #12 : Iunie 29, 2010, 17:43:11 »

Ai dreptate, mersi pentru sesizare. Am modificat sursa oficială. Smile
Memorat
marius21
Strain
*

Karma: -20
Deconectat Deconectat

Mesaje: 27



Vezi Profilul
« Răspunde #13 : August 30, 2010, 14:20:58 »

Lucru dubios... dupa cum s-a mai zis... merge si fara ciur... Cred ca ar trebui revizuite testele... Macar unul sa fie la limita si sa le grupati pe ultimele 3 ca sa se ia 70
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #14 : August 30, 2010, 20:28:47 »

Lucru dubios... dupa cum s-a mai zis... merge si fara ciur... Cred ca ar trebui revizuite testele... Macar unul sa fie la limita si sa le grupati pe ultimele 3 ca sa se ia 70

Din păcate nu se prea poate face diferențierea între soluțiile care folosesc ciurul și cele care nu-l folosesc. Pe ultimele 2 teste numerele sunt aproape de limita maximă, așa că nu prea văd cum am putea scoate un test la limită. Dacă ai vreo propunere, ea este binevenită. Smile
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #15 : August 30, 2010, 22:04:30 »

Fiecare n sa aiba un divizor prim > sqrt(n). Asta e probabil maximul care se poate face fara prea mult efort.
Si totusi, nu cred ca are foarte multa relevanta faptul ca merge si fara ciur. Ideea acestei probleme e sa te invete ca putina matematica aduce intotdeauna eleganta si eficienta. Ciurul are problema lui separata.

Cred ca toate problemele din arhiva educationala ar trebui abordate astfel: nu 'sa se invete o problema' , ci sa se faca o mica conexiune. Multi incepatori, dupa ce rezolva Numerele lui Stirling de ex. , isi spun 'Hah, stiu numerele lui stirling'. Si defapt poti ramane cu mai multe, gen 'uite frate, unele probleme de combinatorica merg mana in mana cu programarea dinamica si imi pare si logic fiindca etc etc'.

Dupa parerea mea, ar trebui incurajata chestia asta, dar recunosc ca nu prea am idee cum.

Ma scuzati pentru postul prea lung( probabil am si exagerat putin cu ce am spus), dar am ramas cu impresia ca multi utilizatori ( dintre cei mai noi, intr-adevar ) vad arhiva educationala ca ' Informatica in X pasi simpli ' sau alte lucruri de genul. Ori nu e asa.

Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #16 : August 30, 2010, 22:38:41 »

Am incercat sa fac eu un test dupa ce a spus Mihai, dar vad ca se comporta destul de bine solutia . Si oricum nu conteaza ca merge si fara ciur .... ideea trebuie prinsa ...
Cod:
10
68763841323
45603526978
68405290467
91207053956
91208055748
68405327187
69680635382
89447799118
94358007946
99968268298
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #17 : August 31, 2010, 09:36:21 »

Singura soluție care ar merge în acest moment ar fi să schimb structura testelor, ceea ce ar însemna ca toată lumea să retrimită soluțiile => nu merită. Cum a zis și Mihai, pentru ciur există o problemă separată, ideea acestei probleme fiind cu totul alta.

Îmi cer scuze pentru neplăcerile cauzate.
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #18 : August 31, 2010, 10:14:35 »

Singura soluție care ar merge în acest moment ar fi să schimb structura testelor, ceea ce ar însemna ca toată lumea să retrimită soluțiile => nu merită. Cum a zis și Mihai, pentru ciur există o problemă separată, ideea acestei probleme fiind cu totul alta.

Îmi cer scuze pentru neplăcerile cauzate.
Admini pot reevalua problemele daca numarul de surse nu depaseste o anumita limita. M-am uitat acuma si vad ca la problema asta numarul de surse nu depaseste acea ca poti sa schimbi testele si sa rogi un admin sa reevalueze.
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #19 : August 31, 2010, 10:38:38 »

Admini pot reevalua problemele daca numarul de surse nu depaseste o anumita limita. M-am uitat acuma si vad ca la problema asta numarul de surse nu depaseste acea ca poti sa schimbi testele si sa rogi un admin sa reevalueze.
Din ce văd, și ownerii taskului pot face reevaluarea. Voi reface zilele acestea testele și voi reevalua. Smile
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #20 : August 31, 2010, 18:37:59 »

Se pot reevalua toate sursele trimise la o problema, insa nu mai mult de 500 (?) deodata. Se pot folosi filtrele job_begin si job_end pentru a imparti problemele in grupuri care sa respecte limita maxima de surse.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #21 : August 31, 2010, 21:15:15 »

Am modificat testele, acum sper să nu mai fie probleme și am dat un reeval. Îmi cer scuze pentru neplăcerile cauzate.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #22 : Ianuarie 17, 2011, 21:51:53 »

A/B = A * B-1

Tu ai de calculat valoarea % M a sumei.

(A/B)%M= [(A % M) * (B-1 % M)] % M

Acel B-1 reprezinta inversul modular al lui B. ( B * B-1 % M = 1, B-1 e intreg )
Acest lucru e folositor pentru ca poti retine doar valoarea modulo M a valorii lui A si B fara a avea probleme cu memoria (sa iasa din long long).
Asa ceva  Smile... sper ca te-a ajutat.
Memorat
tzipleatud
De-al casei
***

Karma: 104
Deconectat Deconectat

Mesaje: 117



Vezi Profilul
« Răspunde #23 : August 20, 2011, 20:26:29 »

Salut! Imi zice si mie cineva de ce sursa asta http://infoarena.ro/job_detail/609359?action=view-source ia TLE pe un test, va rog? Multumesc anticipat!
Memorat
soriyn
Vorbaret
****

Karma: 24
Deconectat Deconectat

Mesaje: 150



Vezi Profilul
« Răspunde #24 : August 20, 2011, 21:06:01 »

Cred ca din cauza vectorului ala ciur. Incearca sa folosesti bitset din STL.
Memorat
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines