题解 | #最简真分数#

最简真分数

https://www.nowcoder.com/practice/1f1db273eeb745c6ac83e91ff14d2ec9

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;

int a[2000];

//将问题转换为求最大公约数
int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

int main() {
    int n, i, j, sum;
    while (scanf("%d", &n) != EOF && n != 0) {
        for (i = 0; i < n; i++) scanf("%d", &a[i]);
        for (i = 0, sum = 0; i < n; i++) {
            for (j = i + 1; j < n; j++) { //如果最大公约数为1,说明不能再化简了
                if (gcd(a[i], a[j]) == 1) sum++;
            }
        }
        printf("%d\n", sum);
    }
    return 0;
}

全部评论

相关推荐

07-15 14:14
门头沟学院 Java
7.10投递7.15感谢信
投递地平线等公司7个岗位
点赞 评论 收藏
分享
醉蟀:你不干有的是人干
点赞 评论 收藏
分享
06-26 15:33
青岛工学院 Java
积极的秋田犬要冲国企:他现在邀请我明天面试
点赞 评论 收藏
分享
07-18 10:39
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务