898 Suman

[•wefgef]

Aici puteti discuta despre problema Suman.

[•miculprogramator]

Ma poate ajuta cineva la problema asta ? Prima data am incercat un brute, apoi am cautat o formula ... Nu ma prind cum se face.   

[•CezarMocan]

Principiul includerii si excluderii 

[•Anamaria20]

Am rezolvat problema folosind principiul includerii si excluderii dar iau mai multe TLE-uri. Cum ati calculat CMMMC a k numere? Cred ca acolo gresesc...   

[•Dastas]

CMMMC(a, b) = (a*b)/CMMDC(a, b)

CMMMC(a, b, c) = CMMMC( CMMMC(a, b), c )
CMMMC(a, b, c, d) = CMMMC{ CMMMC[ CMMMC(a, b), c ], d }

... etc.

Ar trebui sa fie suficient de rapid asa.

[•benny]

Care este principiul includerii si excuderii?

[•toni2007]

S-a mai postat, puteai sa dai si tu un search.

[•SebiSebi]

Cat trebuie sa dea pentru:

Cod:

1000000
4
2
3
5
7

Cod:

10000
4
2
3
5
7

Cod:

100000
8
2
3
5
7
10
12
101
451

Multumesc!

[•vendetta]

Cod:

 
1 : 385715214279
2 : 38583585
3 : 3870913584

[•SebiSebi]

Imi da corect, insa iau 0 puncte. Principiul este urmatorul : consider k multimi A1, A2, ... ,Ak formate din numerele mai mici ca N si care nu sunt prime cu v[k]. Fie S1,S2, ... ,Sk suma numerelor ce alcatuiesc multimea corespunzatoare, pe care le aflu cu formula de la progresii geometrice. Folosind principiul includerii si excluderii aflu reuniunea multimilor A1, A2, ... ,Ak si in aceesi timp suma finala S. Nu inteleg ce gresesc.
Pentru

Cod:

1000000000
20
2
3
5
7
11
13
19
37
181
666013
17
23
29
43
37
31
313 
701
1039
431

Trebuie sa dea:

Cod:

428339514268744659

Multumesc!

[•SpiderMan]

Dap, e bine.

[•stoianmihail]

Un test pe care se ia usor TLE:

1000000000
20
999999999
999999997
999999993
999999997
999999999
999999993
999999999
999999993
999999997
999999999
999999999
999999997
1000000000
999999999
999999997
999999997
999999999
999999993
999999997
999999997

Raspuns: 9634934603

[•stoianmihail]

Iertati-ma daca nu stiu sa editez un comentariu! Raspunsul la testul trecut este defapt: 3999999989. 

[•andreistan]

Ce complexitate trebuie sa aiba?