Problemi 107

Kërkesa

Një qenush gjeti një arkë me N monedha. Ai nuk e hap dot vetë, por mund të lehë që tu tërheq vëmendjen njerëzve që ndodhen aty pranë. Ai e di që njerëzit do marrin secili një sasi të barabartë monedhash, dhe të tjerat do ti lënë në shesh, kështu që ai mund ti marrë.

Qenushi mund ta ndryshojë fortësinë e të lehurit, në mënyrë që ti tërheqë vëmendjen 1 personi, ose 2 personave, e kështu me radhë, deri në K persona. Sa persona duhet të thërrasë, në mënyrë që në fund ti ngelen sa më shumë monedha?

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

Shembull

$ cat input.txt
2
5 2
11 3

$ python3 prog.py < input.txt
1
2

Zgjidhja

T = int(input())
for t in range(T):
    N, K = map(int, input().split())
    m = 0
    for k in range(1, K+1):
        if N % k > m:
            m = N % k
    print(m)