互质数（函数）

Sg认识到互质数很有用。若两个正整数的最大公约数为1，则它们是互质数。要求编写函数判断两个整数是否互质数。

输入格式:

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试先输入1个整数n（1≤n≤100），再输入n行，每行有一对整数a、b（0<a，b<109）。

输出格式:

对于每组测试数据，输出有多少对互质数。

输入样例:

1
3
3 11
5 11
10 12

输出样例:

2

来源：

[1] 黄龙军, 等. 大学生程序设计竞赛入门—C/C++程序设计（微课视频版）, 北京:清华大学出版社, 2020.11. ISBN:9787302564744
[2] 黄龙军.程序设计竞赛入门（Python版）,北京:清华大学出版社,2021.4. ISBN:9787302571230

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

C程序如下：

#include <stdio.h>

int gcd(int a, int b);//判断互质数

int main(void)
{
    int t;
    scanf("%d", &t);//输入要测试的组数
while(t--)
{
    int n;
    scanf("%d", &n);//输入要测试几组数
    int count = 0;//定义一个用来计数的变量
    while(n--)
    {
        int a, b;
        scanf("%d%d", &a, &b);//输入每一对要测的数
        if(gcd(a, b) == 1)
        {
            count ++;//是互质数则记一次数
        }
    }
    printf("%d\n", count);//输出最终有多少对互质数
}
    return 0;
}

int gcd(int a, int b)//辗转相除法求最大公约数
{
    int c = a % b;//定义一个新的变量，用来储存a除b的余数
    while(c!=0)//若c为零则推出循环
    {
        a = b;//将b的值赋给a
        b = c;//再a除b的余数赋值给b
        c = a % b;//得到新的余数
    }
    return b;//最终b为这两个数的最大公约数，若b为1则这两个数为互质数
}