欧几里得算法

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数

程序设计编辑

辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
⒈ 若 r 是 a ÷ b 的余数，且r不为0， 则
gcd(a,b) = gcd(b,r)
⒉ a 和其倍数之最大公因子为 a。
另一种写法是：
⒈ 令r为a/b所得余数（0≤r
若 r= 0，算法结束；b 即为答案。
⒉ 互换：置 a←b，b←r，并返回第一步。

辗转相除求最大公因数 化简函数

#include <stdio.h>
void simple(long long int m,long long int n);
int main()
{
    simple(x,y);
}
void simple(long long int m,long long int n)
{
    long long int a = m;
    long long int b = n;
    long long int t;
    t =a%b;
    while(t!=0)
    {
        a=b;
        b=t;
        t=a%b;  
    }
    long long int end = b;
    m=m/end;
    n=n/end;
    if(m==0) printf("0 0\n");
        else printf("%lld %lld\n",m,n);
}