Problem B
Miller-Rabin

Languages en is

Ákvarðið hvort heiltala $a$ er Miller-Rabin vitni fyrir heiltölu $n$ .

Inntak

Fyrsta línan inniheldur fjölda tilrauna $1 \leq t \leq 10^{5}$ . Hver tilraun samanstendur af tveimur línum: Fyrsta línan inniheldur heiltölu $3 \leq n \leq 2^{63} - 1$ . Seinni línan inniheldur heiltölu $1 \leq a \leq min {n - 1, 2^{31} - 1}$ .

Úttak

Skrifið línu fyrir hverja tilraun, með $1$ ef $a$ er Miller-Rabin vitni fyrir $n$ , eða $0$ ef ekki.

Sample Input 1	Sample Output 1
2 561 2 172947527 17	1 0

Hide

Please log in to submit a solution to this problem

Log in

CPU Time limit1 second

Memory limit1024 MB

?

DifficultyNot Available

LinksStatistics

DownloadsSample data files

Source & LicenseJón Steinn ElíassonT-513-Cryptography and Number Theory

You haven't made any submissions on this problem yet.

Editor:

Problem BMiller-Rabin

Inntak

Úttak

Problem B
Miller-Rabin