048 Suma si numarul divizorilor

[•PlayLikeNeverB4]

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

[•tzipleatud]

Am utilizat bitset si am reusit. Multumesc frumos! 

[•Magnus]

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.

[•blue_phoenix]

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! 

[•SpiderMan]

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

[•blue_phoenix]

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

[•RedoxGFXx]

#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;}}

[•k_ounu_eddy]

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

Cod:

if(n > 1)
	{
		nd *= 2;
		sd = (1LL*sd*(n + 1)) % MOD;
	}

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

[•Vali_Deaconu]

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

Cod:

if(n > 1)
	{
		nd *= 2;
		sd = (1LL*sd*(n + 1)) % MOD;
	}

[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? 

[•Bogdanisar]

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

1
99799811

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