回分類題庫
d181: CP Lab Exercise: GCD
出處:

Difficulity : 1
Accepted : 86 Times | Submit :275 Times | Clicks : 1690
Accepted : 77 Users | Submit : 80 Users | Accepted rate : 96%
Time Limit :10000 ms | Memory Limit : 64000 KBytes
題目加入時間 : 2010-10-20 15:24

Content :

                   x, y = 0 and x != 0
gcd(x, y) = {y, x = 0 and y != 0
                  gcd(y, remainder(x, y)), y > 0

remainder(x, y) is the remainder of x / y

You have to write a recursive gcd function to pass the exercise.

int gcd( int, int );

 

 

Input :

The first line is a positive number N: the number of the sets.

The following N lines are the test data. Each line is a set of input data consist of two positive integers a and b.

Your job is to compute the gcd of a and b.

You can assume the inputs are valid.

Output :

For each set of input, you have to output a line of the result.

Sample Input :

2
2 3
5 10

Sample Output :

1
5

Hint :


  

Author :


  Solve it!   Status Forum (0)

C++
C
JAVA
57914. CC501 (4 ms , 226KB)
46726. sy2es956304 (6 ms , 362KB)
27744. hsnu114444 (6 ms , 358KB)
76574. tico88612 (8 ms , 362KB)
67774. cp100703009 (8 ms , 358KB)
31661. q0423546006 (2 ms , 224KB)
30168. alopex (2 ms , 230KB)
27214. cp99703008 (2 ms , 226KB)
26487. cp99703034 (2 ms , 232KB)
26376. cp97302012 (2 ms , 230KB)
57918. nwgs524513cja (82 ms , 148KB)
57899. nwgs524513cja (98 ms , 172KB)
50453. nwgs524513cja (100 ms , 158KB)

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡