题解 | #最简真分数#

最简真分数

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;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 11:21
被夸真的超级开心,好可爱的姐姐
码农索隆:老色批们不用脑补了,我把金智妮的图找来了查看图片
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 14:00
不想多说了,什么逆天HR,还要教我礼貌😂
机械打工仔:这不纯傻卵吗,他还操心上别人老板了
投递BOSS直聘等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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