Problemi 108

Kërkesa

Çufoja ka bërë N copa keku të vogla dhe tani po mendon si ti paketojë. Çdo paketë duhet të ketë numër të njëjtë kekësh. Çufoja duhet të zgjedhë një numër të plotë A, nga 1 në N, dhe duhet të vendosë fiks A copa keku në çdo paketë. Pasi ka plotësuar aq paketa sa të jetë e mundur, copat e kekut që kanë mbetur pa paketuar Çufoja mund ti hajë vetë. Çufos i pëlqejnë shumë këta dreq kekë. Sa duhet ta zgjedhë numrin A të paketimit që ti mbeten sa më shumë copa keku për të ngrënë?

Bëni një program që merr numrin N dhe gjen numrin A, ku \(2 \leq N \leq 100000000 (10^8)\) Ky program duhet ta kthejë përgjigjen në më pak se 1 sek.

Referenca: https://www.codechef.com/problems/MUFFINS3

Shembull

$ cat input.txt
2
2
5

$ python3 prog.py < input.txt
2
3

Zgjidhja 2

Sqarime

Zgjidhja e parë është e ngadaltë kur N-ja është shumë e madhe, p.sh. kur N=100000000 (provojeni!). Kurse zgjidhja e dytë është jashtëzakonisht e shpejtë, sepse nuk i provon të gjitha rastet por e gjen përgjigjen me formulë.