文章

4

粉丝

209

获赞

2

访问

2.4k

头像
最简真分数 题解:有个疑问
P1180 北京大学/北京航空航天大学机试题
发布于2024年3月12日 13:47
阅读数 530

#真分数不是要求分母大于分子吗

#对于 if(IsHuzhi(arr[i],arr[j])) ,这样可以AC

#为什么变成if(arr[j] > arr[i] &&IsHuzhi(arr[i],arr[j])),加上了分母大于分子的判断反而答案错误?

 

#include<math.h>
int IsHuzhi(int x,int y){
    for(int i = 2;i <= x;i++){
        if(x % i == 0 && y % i == 0){
            return 0;
        }
    }
    return 1;
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        int arr[n];
        for(int i = 0;i < n;i++){
            scanf("%d",&arr[i]);
        }
        int count = 0;
        for(int i = 0;i < n;i++){
            for(int j = i+1;j < n;j++){
             if(IsHuzhi(arr[i],arr[...

登录查看完整内容


登录后发布评论

1 条评论
snake VIP
2024年3月12日 15:45

因为你这个代码已经保证了任意两个数只会使用一次

 for(int j = i+1;j < n;j++)

如果你把j改为从0开始就需要加上

if(arr[j] > arr[i] &&IsHuzhi(arr[i],arr[j]))

对于任意两个数,只需要把小的那个做分子就行,保证不重复计算即可

赞(1)