互质数(函数)

发布时间:2023年12月17日

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则这两个数为互质数
}

文章来源:https://blog.csdn.net/2302_80325489/article/details/135036091
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。