最大公约数，相信大家高中的时候就知道了，如何用计算机来快速求解两个数的最大公约数是一个很常见的数学问题。

如果题目要求我们求两个数x和y的最大公约数，我们只需要记住下面这种方法就行了。

#include <stdio.h>  
  
int gcd(int a, int b) {  
    if (b == 0) return a;  
    else return gcd(b, a % b);  
}  
int main() {  
    int x, y;  
    scanf("%d%d", &x, &y);  
    printf("%d\n", gcd(x, y));  
}  

显然，大部分时候题目都不会出的这么直接，那么对于最大公约数一般会有哪些变形考法呢？

最简真分数
题目描述：
给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。
输入描述：
每组包含n（n<=600）和n个数，整数大于1且小于等于1000。
输出描述：
每行输出最简真分数组合的个数。
输入样例#:
7
3 5 7 9 11 13 15
输出样例#:
17
题目来源：
DreamJudge 1180

题目解析：通过分析题意可以发现，最简真分数的必要条件就是不可以继续约分，那么不可以继续约分，就说明分子和分母的最大公约数为1。因此，我们只需要枚举所有组合的情况然后判断GCD即可。

参考代码

#include <stdio.h>  
  
int gcd(int a, int b) {  
    if(b==0) return a;  
    else return gcd(b, a%b);  
}  
int main() {  
    int buf[605];  
    int ans, n;  
    while(scanf("%d", &n)!=EOF) {  
        for(int i=0; i<n; i++)  
            scanf("%d", &buf[i]);  
        ans=0;//答案个数  
        for(int i=0; i<n; i++)  
            for(int j=i+1; j<n; j++)  
                if (gcd(buf[i], buf[j])==1) ans++;  
        printf("%d\n", ans);  
    }  
    return 0;  
}  

另一种变形考法是：分数化简

例如：给你一个分数12/30，让你将它化简，很明显，我们都知道它的答案是2/5。
那么：如果给你一个分数x/y呢？如何化简？

我们可以得出：

x/y = (x/gcd(x,y))/(y/gcd(x,y))

那么只用求出他们的最大公约数，然后除一下就可以得到答案了。

学会求最大公约数（GCD）