Diferente pentru summer-challenge-unu/solutii intre reviziile #9 si #10

Nu exista diferente intre titluri.

Diferente intre continut:

Aceasta problema a fost considerata cea mai simpla din concurs, in special pentru ca realizarea unui program experimental care simula pasii din problema ne arata ca usile ce raman inchise au ca index un patrat perfect.
Pentru a demonstra aceasta afirmatie avem nevie de cateva cunostinte minore de teoria numerelor.
Pentru a demonstra aceasta afirmatie avem nevoie de cateva cunostinte minore de teoria numerelor.
La fiecare pas $i$ directorul va vizita toti multiplii lui {$i$}, ceea ce inseamna ca un anumit numar $X4 va fi vizitat la pasii ai caror indecsi il divid pe {$X$}. Deci pentru a afla cate usi vor fi deschise in final va trebui sa numaram cate numere au un numar par de divizori. Pentru acest lucru ne va si mai usor sa numaram cate au un numar impar de divizori urmand sa le scadem din {$N$}. Stim ca daca descompunem un numar $X$ in factori primi: {$X=F{~1~}^P{~1~}^*F{~2~}^P{~2~}^*...*F{~t~}^P{~t~}^$} numarul de divizori ai sai va fi {$D=(P{~1~}+1)*(P{~2~}+1)*...*(P{~t~}+1)$}. Pentru ca $D$ sa fie impar trebuie ca fiecare factor al produsului sa fie deci $P{~i~}+1$ impar ceea ce inseamna ca exponentii factorilor primi din descompunere vor fi pari. {$X=F{~1~}^2*P'{~1~}^*F{~2~}^2*P'{~2~}^*...*F{~t~}^2*P'{~t~}^ = (F{~1~}^P'{~1~}^*F{~2~}^P'{~2~}^*...*F{~t~}^P'{~t~}^)^2^$}. Inseamna ca $X$ va fi patrat pefrect.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.