infoarena

Aici puteţi discuta despre problema Suma si numarul divizorilor (http://infoarena.ro/problema/ssnd).

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? :)

p_n^d_n+1-1=(p_n-1)*(p_n^d_n+p_n^d_n-1+p_n^d_n-2+...+d_n+1)
Aşadsar (p_n^d_n+1-1)/(p_n-1)=p_n^d_n+p_n^d_n-1+p_n^d_n-2+...+d_n+1 şi nu trebuie folosit inversul modular.

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.

ma poate ajuta si pe mine cineva va rog? nu inteleg ce gresesc aici

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

n[l], dupa ce l-ai descompus in factori primi, poate fi mai mare ca 1, ai uitat cazul asta :)

 ](*,) ](*,) ](*,)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:(:(:(

are cineva vre-o idee???? :annoyed:  :-s :-s

corectie 2 incorecte si tre TLE

 Nu posta succesiv pe acelasi subiect. Modifica mesajele anterioare!

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.

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


cu asta

Ai dreptate, mersi pentru sesizare. Am modificat sursa oficială. :)

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ă. :)

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.

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 ...

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.

Din ce văd, și ownerii taskului pot face reevaluarea. Voi reface zilele acestea testele și voi reevalua. :)

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.

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

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  :)... sper ca te-a ajutat.

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

Cred ca din cauza vectorului ala ciur. Incearca sa folosesti bitset din STL.

Exact, cu bitset sau poti imbunatati ciurul (cum am facut eu :D)

Am utilizat bitset si am reusit. Multumesc frumos!  :D

noul timp e bun pt problema asta (cele 100 de puncte pot fi luate), dar ar trebui schimbata sursa oficiala (http://infoarena.ro/job_detail/616025) care pica pe 3 teste.

Salutare,

am implementat solutia, sursa e aici: http://infoarena.ro/job_detail/626840?action=view-source

problema e ca de la testul 5 in colo, iau killed by signal 8. din cate am vazut pe internet asta inseamna ca, la un mom dat in program am facut un calcul/adunare/inmultire care a iesit din spatiul unui long int (eu am fol numai long int-uri).
oricat de simpla ar parea intrebarea, nu ma prind unde s-ar putea intampla asta, mai ales ca mie, pentru datele de la testul 5 cel putin, nu-mi da nicio eroare (l-am compilat+rulat de pe linux si pare ok, mi-a dat bine la iesire)
Orice parere/indicatie de unde ar putea veni problema e bine venita!  :)

Ti-am obtinut 70 puncte (http://infoarena.ro/job_detail/626887?action=view-source), pentru 100 trebuie exponentiere in timp logaritmic (cred, desi nu e necesar  :-k), te mai uiti tu pe acolo, dar oricum ideea e urmatoarea : tu ai avut in procedura ssnd ceva gen long int n, care e gresit (dupa cum vezi, mai jos chiar tu l-ai pus long long, pentru ca el e maxim 10¹², ceea ce depaseste int <<sau long int, care dupa noile standarde e tot aia>>), deci trebuie pentru inceput in acea functie sa schimbi long long n. Bun, acum, tu ai ceva gen (in while) prim[ i ] * prim[ i ] <= n, ceea ce e prost, pentru ca prim[ i ] = int si n = long long, si cand se evalueaza prim²[ i ], daca prim[ i ] e suficient de mare, o sa-ti dea un numar total aiurea, adica daca depaseste int-ul, o sa o ia din celalalt capat (adica de la minus 2³¹). Asadar, daca vrei ca membrul stang sa fie tot long long, ai 2 variante : ori faci (long long) prim[ i ] * prim[ i ] <= n (care, dupa cum vezi, "converteste" acel produs la long long), sau, ceea ce si eu prefer, 1LL * prim[ i ] * prim[ i ] <= n (si ceea ce ai si in cod, pentru ca 1LL inseamna numarul unu convertit la long long, si dupa cum ai un produs de long long si int, rezultatul e tot timpul luat de cel mai mare tip, adica long long). Am facut asa si cand ai calculat suma, pentru ca acel produs depaseste int, dar, din fericire, ai modulo, si cand aplici aceasta operatie, o sa ai un numar mai mic decat numarul la care faci modulo, cazul asta 9973, care intra si in short (dar, repet, trebuie sa faci asta pentru ca poti avea : 123456789123 % 9973, care da e un numar mic, dar din pacate acel numar pentru care este aplicat modulo e mai mare decat int, si trebuie sa fie convertit la long long). Cam asta e, incearca solutia pentru 100 puncte, explicata acolo, si sper ca ai inteles ce am vrut sa zic. Spor ;).

[L.E.] Se pare ca ti-am scos 100 pct pana la urma (http://infoarena.ro/job_detail/626906?action=view-source), am folosit dupa cum vezi urmatoarea chestie : in acel for, daca n nu se imparte exact la prim[ i ] atunci nu il mai las sa continue degeaba, face multe operatii aiurea (o comparare din acel while, si o inmultire fara rost), si am mai pus i < k in acel for (adica sa nu depasesc limita vectorului prim[ i ], desi nu cred ca e o problema daca nu ai pune acea conditie).

Multumesc frumos! :)
nu ma asteptam sa conteze atat de mult niste impartiri; ma gandisem si eu sa pun un if acolo, dar am vazut ca formula avea sens si mergea si daca factorul era la puterea 0 :D

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f("ssnd.in");
    ofstream g("ssnd.out");
    int v[50],i,t,s,nr,j;
    f>>t;
    for(i=1;i<=t;i++){
        f>>v;
        s=0;
        nr=0;
        for(j=1;j<=v;j++){
        if(v%j==0){
            nr++;
            s+=j;
        }}
        g<<nr<<" "<<s<<endl;}}

Nu am inteles exact bucatica aceasta de cod, imi explica cineva, va rog?


[EDIT]: De ce nd se inmulteste cu 2?

Înseamnă că la descompunerea în factori primi ai lui N, s-a găsit factorul prim n (n != N) la puterea 1, deci se înmulțește numărul divizorilor cu 2, adică e+1, unde e = exponentul lui n, adică 1.
Pentru suma divizorilor, se calculează conform formulei, fără să se aplice invers modular.


A făcut cineva problema pe euclid extins? Eu nu pot să iau decât 70 de puncte... Pe inversul cu mod-2 iau 100, dar sunt curios, de ce nu merge și pe euclid extins?  :-k

Am gasit un test pe care solutia de 100 de puncte da un rezultat gresit  :D

1
99799811

Aceasta da:
4 -9938
Cand corect este:
4 35