Problem I/S. 52. (March 2021)

I/S. 52. Subscribers can reach the text of the problem after signing in. The text will be public from March 28, 2021.]

(10 pont)

Deadline expired on April 15, 2021.

Sorry, the solution is available only in Hungarian. Google translation

Horcsin Bálint megoldása:

Látható, hogy csak azok a megfelelő x, y párok, amelyekre \(\displaystyle \frac{y}{x}=p\) prím. Átrendezve \(\displaystyle \frac{y}{p}=x\). Vagyis ha megállapítjuk, hogy egy \(\displaystyle y\)-nnak hány egymástól páronként eltérő prím osztója van, és ezt minden \(\displaystyle y\in [2,n]\)-re összegezzük, akkor megkapjuk a feladat megoldását. De ezzel megegyezik, ha minden prímre megnézzük, hogy hány számnak osztója a \(\displaystyle [2,n]\) intervallumon. Egy adott \(\displaystyle p\) prímre ezen számok darabszáma \(\displaystyle \left\lfloor \frac{n}{p}\right\rfloor\). A prímeket Erathostenes szitájával megkereshetjük, és az eredményeket ősszegezhetjük.

Komplexitás: Erathostenes szitájának futásideje \(\displaystyle \mathcal{O}(N*log(log(N)))\), és ezen kívül csak konstans műveleteket végzünk, így a megoldás futásideje is \(\displaystyle \mathcal{O}(N*log(log(N)))\).

Statistics:

12 students sent a solution.
10 points:	Horcsin Bálint, Kovács Alex, Melján Dávid Gergő, Tóth 057 Bálint, Ürmössy Dorottya, Varga 256 Péter.
6 points:	1 student.
5 points:	1 student.
3 points:	2 students.
0 point:	2 students.

Problems in Information Technology of KöMaL, March 2021