Fiind vorba de maxim $1.000.000$ numere se poate calcula pentru fiecare in parte cati divizori primi are. Pentru acest lucru se foloseste ciurul lui Erathostene si se construieste vectorul {$ndp{~i~}$} - numarul de divizori primi ai lui {$i$}. Parcurgem numerele din $1$ in $1$ si in momentul in care am dat peste un numar care are $0$ divizori primi pana in acest moment inseamna ca am gasit un nou numar prim si vom actualiza vectorul $ndp$ pentru toti multiplii lui si implicit pentru el (numarul fiind propriul sau divizor). Apoi se construieste o matrice $sol{~i,j~}$ care retine care este cel mai mare numaru mai mic sau egal cu $i$ cu $j$ divizori primi (adica exact raspunsurile pentru problema noastra). Pentru a construi linia $i$ se copiaza linia $i-1$ si se actualizeaza {$sol{~i,ndp{~i~}~}=i$}.

Pentru mai multe detalii despre cum functioneaza ciurul lui Erathostene puteti accesa "articolul":http://infoarena.ro/Ciurul_lui_Erathostene.

Pentru mai multe detalii despre cum functioneaza ciurul lui Erathostene puteti accesa "articolul":http://infoarena.ro/Ciurul-lui-Erathostene.

h2. Subsir 2

$S2 = a * n + S1$ => {$S1 + S2 = 2 * a * n$}.

Se foloseste o singura data ciurul lui Erathostene pentru a determina functia phi pentru toate intrebarile. Se poate consulta "articolul":http://infoarena.ro/Ciurul_lui_Erathostene despre cirulul lui Erathostene.

Se foloseste o singura data ciurul lui Erathostene pentru a determina functia phi pentru toate intrebarile. Se poate consulta "articolul":http://infoarena.ro/Ciurul-lui-Erathostene despre cirulul lui Erathostene.

O alta solutie, propusa de Bogdan A. Stoica, se bazeaza pe principul includerii si excluderii. Din enuntul problemei ne dam seama ca suma ceruta este suma tuturor numerelor $z$ cu proprietatea ca {$cmmdc(z, x) = 1$}. Pentru a afla aceste numere este de ajuns sa observam ca $cmmdc(z, x) != 1$ daca si numai daca exista cel putin un $p{~i~} = q{~j~}$ unde {$z = p{~1~}^e{~1~}^&#0042; ... &#0042;p{~n~}^e{~n~}^$}, iar {$x = q{~1~}^f{~1~}^&#0042; ... &#0042;q{~m~}^f{~m~}^$}. Fie doua astfel de numere {$p{~i~} = q{~j~}$}. Noi trebuie sa afla suma tuturor numerelor care se divid cu $p{~i~}$ si sunt in intervalul [{$0, 2*x$}]. Aceste numere sunt : {$p{~i~}, 2&#0042;p{~i~}, ..., k&#0042;p{~i~}$}, {$0 < k &le; [2&#0042;x/p{~i~}]$}. Suma acestor numere se poate scrie ca {$p{~i~} + ... + k&#0042;p{~i~}$}, adica pi(1+...+k) adica {$p{~i~}&#0042;k(k+1)/2$}. De aici suntem tentati sa credem ca suma ceruta (fie aceasta {$S$}) este $S$ = {$x(2&#0042;x-1) - p{~1~}&#0042;k{~1~}&#0042;(k{~1~}+1)/2 - .... - p{~n~}&#0042;k{~n~}&#0042;(k{~n~}+1)/2$}. La o citire mai atenta observam ca am scazut unele de doua ori (cele care se divid si cu $p{~1~}$ si cu {$p{~2~}$}, de exemplu) si nu am scazut deloc alte numere care au un divizor comun cu $x$ mai mare decat $1$ (cele care se divid simultan cu {$p{~1~}$}, $p{~2~}$ si {$p{~3~}$}, de exemplu). Astfel, aplicand principiul includerii si excluderii putem schita formula finala : {$S = x&#0042;(2x-1) - p{~1~}&#0042;k{~1~}&#0042;(k{~1~}+1)/2 - ... + p{~1~}&#0042;p{~2~}&#0042;k'{~1~}(k'{~1~}+1)/2 + ... - p{~1~}&#0042;p{~2~}&#0042;p{~3~}&#0042;k''{~1~}(k''{~1~}+1)/2 + ...$}, adica vom scadea toti termenii care se obtin prin inmultirea a unui numar impar de factori primi si vom aduna restul. Aceasta solutie obtine in jur de $80$ de puncte pe restul testelor depasind timpul de executie.