Neutriinoradar

문제

Mõne aja eest leidsid astronoomid tähe $\zeta \backslash zeta$-2019A, millel on $NN$ planeeti. Nüüd avastati, et üks neist planeetidest on eluks kõlbulik. Täht on aga nii kaugel, et selle planeete saab uurida ainult võimsa neutriinoradariga.

Radar töötab järgmiselt. Algul saadab radar tähesüsteemi suunas neurtiinovoo, mida iseloomustavad täisarvulised parameetrid $XX$ ja $YY$. Tähesüsteemilt tagasi peegeldunud signaali analüüsides on võimalik sellest eraldada täisarv $B=\gcd (X,A+Y)B\; =\; \backslash gcd(X,\; A\; +\; Y)$, kus $AA$ on eluks kõlbuliku planeedi järjekorranumber (planeedid on nummerdatud $1\dots N1\; \backslash ldots\; N$ alates tähele $\zeta \backslash zeta$-2019A lähimast) ja $\gcd (X,Y)\backslash gcd(X,\; Y)$ tähistab arvude $XX$ ja $YY$ suurimat ühistegurit, see tähendab suurimat sellist täisarvu, millega nii $XX$ kui $YY$ jaguvad jäägita. Kuna neutriinovoo väljasaatmine on väga energiakulukas, võib seda teha maksimaalselt 40 korda.

Nüüd on astronoomidel vaja programmi, mis juhiks radarit ja tuvastaks eluks kõlbuliku planeedi numbri. Programmi tuumaks on funktsioon int Locate(int n). Seda funktsiooni kutsutakse välja üks kord, andes parameetrina tähe $\zeta \backslash zeta$-2019A planeetide arvu $NN$, ja funktsioon peab tagastama eluks kõlbuliku planeedi numbri $AA$ ($1\le A\le N1\; \backslash le\; A\; \backslash le\; N$).

Funktsioon Locate võib oma töö käigus kasutada funktsiooni int Scan(int x, int y), mis käivitab radari parameetritega $XX$ ja $YY$ ($1\le X\le {10}^{9}1\; \backslash le\; X\; \backslash le\; 10^9$, $0\le Y\le {10}^{9}0\; \backslash le\; Y\; \backslash le\; 10^9$) ning tagastab radarisignaali analüüsi tulemuse $B=\gcd (X,A+Y)B\; =\; \backslash gcd(X,\; A\; +\; Y)$. Funktsiooni Scan võib kasutada maksimaalselt 40 korda.

Testimiskeskkonnas on antud näitefailid, kus vajalikud funktsioonid on juba kirjeldatud ja vaja on lisada ainult funktsiooni Locate realisatsioon. Lisaks võib lahenduse faili kirjutada ka oma funktsioone. Oma lahenduse oma arvutis testimiseks on ka hindamisprogrammi näide, mille sisendi ja väljundi kirjeldus on toodud allpool (serveris on kasutusel teine hindamisprogramm, mis kontrollib ka lahenduse tagastatud vastuse õigsust). Oma lahenduse oma arvutis kompileerimiseks ja testimiseks:

입력

Tekstifaili ainsal real on kaks täisarvu: tähe $\zeta \backslash zeta$-2019A planeetide koguarv $NN$ ($1\le N\le {10}^{9}1\; \backslash le\; N\; \backslash le\; 10^9$) ja eluks kõlbliku planeedi number $AA$ ($1\le A\le N1\; \backslash le\; A\; \backslash le\; N$).

출력

Tekstifaili väljastatakse hindamisprogrammi ja funktsiooni Locate vahelise suhtluse logi.

5 3

Locate(5)
Scan(3, 6) = 3
Scan(4, 2) = 1
Scan(2, 1) = 2
Scan(4, 5) = 4
result = 3