Egy 8x8-as táblázatot úgy töltünk, hogy a p-edik sorának q-adik oszlopába a p/q szám kerüljön. A lehetséges egyszerűsítések elvégzése után hány különböző szám szerepel a táblázatban?

Nem tudok jobb módszert, minthogy fogsz egy kockás lapot és kitöltöd mind a 64 mezőt.

Amibe olyan szám szerepel, ami már volt korábban, azt besatírozod.

Pl az 1/1-et nem satírozod, de a 2/2, 3/3 stb-t igen.

Na, ha kidobáljuk a számelméletet belőle akkor: menjünk a nevező szerint. Az 1 nevezőjű számok addják az egészeket, abból van 8. Ha a nevező 2,3,5,7 akkor nyilván nem lehet egyszerűsíteni semmivel kivéve saját magával. Pl. 3-as nevezőre az lesz a kérdés hogy 1-8 között hány szám nem osztható 3-al, ugye a 3 és a 6 osztható tehát hat darab nem osztható. Tehát a prím nevezők hoznak 4, 6, 7, 7 darabot egyenként. Ez eddig 32.

Ezek után már csak a 4, 6, 8 számok vannak. Ugyanígy el lehet bánni velük, csak azzal kell vigyázni hogy nem saját magukkal hanem a prímtényezőik bármelyikével lehet egyszerűsíteni. Hát hány olyan szám van 1-8 amiben nincs 2-es prímtényező? Nyilván 4. Tehát a 4 és a 8 egyaránt 4-4-et hoz az asztalra, ilyeneket hogy 3/4, 5/8 stb. Végül a 6-hoz azt kell megnézni hogy hány olyan van 8 és alatt miben nincs se 2-es se 3-as: 2-vel osztható van 4, 3-al osztható 2, mindkettővel 1 tehát összesen 4+2-1 számláló van ami olyan hogy egyszerűsíthető lenne (2/6,3/6,4/6,6/6,8/6) tehát a maradék 3 (1/6,5/6,7/6) nem. A végeredmény tehát 43 lesz.

Az például gond lehet, hogy vannak 1-nél nagyobb számok is a táblázatban

A fi(n)-ben pedig szerepel, hogy "not larger than n"

A táblázat kitöltése max 3 perc, így szerintem ez a leghatékonyabb megoldási mód. Kár ennél több időt vesztegetni a feladatra :)

100x100 esetén már érdemes gondolkodni, de ezt én erőből oldanám meg :)