Nhập hai số tự nhiên m, n không đồng thời bằng 0.

Cho biết ướcsố chung lớn nhất của m và n

Dữ liệu: Vào từ thiết bị nhập chuẩn hai số nguyên không âm m, n  ≤ 10²⁵⁶  (m, n không đồng thời bằng 0)

Kếtquả: Ghi ra thiết bị xuất chuẩn một số nguyên duynhất ước số chung lớn nhất của m và n

Yêu cầu: thời gian chạy chương trình <0.01s

VD1: m=128; n=100 thì kết quả là 4

VD2:(m,n cực lớn có trên hàng trăm chữ số) 

m=27000000000000000000000077000000000000000000000000000000000

00000000000270000000000000000000000770000000000000000000000000

00000000000000000002700000000000000000000007700000000000000000

00000000000000000000000000027000000000000000000000077000000000

00000000000000000000000000000000000125

n=1800000000000000000000000000000099000000000000051800000000000

000000000000000000099000000000000051800000000000000000000000000

00009900000000000005180000000000000000000000000000009900000000000005

thì kết quả là 5

         
a=9999999900099999
b=7777778889999999999
while a!=b:
    if a>b:
        a=a-b
    elif a<b:
      b=b-a
print('UCLN: ', a)

   

         
import time
def biendoi(x, y): #x luôn lớn hơn y
    if x/y>1.1 and x%y!=0:
        x = x % y
    else:
        x = x - y
    return x
def ucln(m,n):
    while m!=n:
        if m>n:
            m=biendoi(m,n)
        elif n>m:
           n=biendoi(n,m)
    return m

t1 = time.time()
fin=open("ucln.inp",'r')
fout=open('ucln.out','w')
m=int(fin.readline())
n=int(fin.readline())
fout.write(str(ucln(m,n)))
fin.close()
fout.close()

t2 = time.time()
print('Thời gian chạy: {} giây'.format((t2 - t1)))