最简真分数

[编程题]最简真分数

热度指数：19241 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。

输入描述:

每组包含n（n<=600）和n个不同的整数，整数大于1且小于等于1000。

输出描述:

每行输出最简真分数组合的个数。

示例1

输入

7
3 5 7 9 11 13 15
3 
2 4 5
0

输出

17 
2

算法知识视频讲解

Java

LHC0512

Java 解法

package nowcoder.demo40;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            int[] arr =new int[n];
            for (int i = 0; i < n; i++) {
                arr[i]=scanner.nextInt();
            }
            int count=0;
            for (int i = 0; i < n; i++) {
                for (int j = i+1; j < n; j++) {
                    if (gcd(arr[i],arr[j])==1)
                       count++;
                }
            }
            System.out.println(count);
        }
    }
    /**
     * 计算最大公因数，辗转相除法
     * 运行时间：120ms
     *
     * 占用内存：12932k
     * */
    static int gcd(int a,int b){
        if(b==0)return a;
        else return gcd(b,a%b);
    }
}

编辑于 2020-03-13 15:52:25 回复(1)

Java

小新没有蜡笔~

重点在于使用辗转相除法求最大公约数
两个数中较大的一个数记为n1，较小的数记为n2
1、mod=n1%n2，若mod=0，则n2为最大公因数
2、n1=n2，n2=mod，转到1

//辗转相除法求最大公因数
    public static int maxFactor(int n1,int n2){
        if(n1<n2){
            int t=n1;
            n1=n2;
            n2=t;
        }
        int mod;
        int shang;
        do{
            mod=n1%n2;
            shang=n1/n2;
            n1=n2;
            n2=mod;
        }while(mod!=0);
        return n1;
    }

发表于 2019-02-14 11:56:06 回复(0)

Java

/xinCupid☆

import java.util.*;
public class Main {
    public static int gcd(int p, int q) {
        if (q == 0)
            return p;
        int r = p % q;
        return gcd(q, r);
    }
    
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        while (reader.hasNext()) {
            int N = reader.nextInt();
            int[] number = new int[N];
            for (int i = 0; i < N; ++i) {
                number[i] = reader.nextInt();
            }
            
            int cnt = 0;
            for (int i = 0; i < N - 1; ++i) {
                for (int j = i + 1; j < N; ++j) {
                    int big = Math.max(number[i], number[j]);
                    int small = Math.min(number[i], number[j]);
                    if (big % small != 0 && gcd(big, small) == 1)
                        cnt++;
                }
            }
            System.out.println(cnt);
        }
    }
}

发表于 2018-04-05 22:49:30 回复(0)

Java

涛仔

public class Main {
	
	public int doSome(int[] lists){
		int count=0;
	loop1:for(int i=0;i<lists.length;i++){
	  loop2:for(int j=0;j<lists.length;j++){
				if(i==j||lists[i]>lists[j]){
					continue;
				}
				if(lists[j]%lists[i]!=0&&lists[i]<lists[j]){
				loop3:for(int k=2;k<=lists[i];k++){
						if(lists[i]%k==0&&lists[j]%k==0){
							continue loop2;
						}else{
							continue;
						}
					}
					count++;
				}
			}
		}
		return count;
	}

	public static void main(String[] args) {
		Scanner s=new Scanner(System.in);
		Main m=new Main();
        while(true){
        	int size=s.nextInt();
        	if(size==0){
        		break;
        	}
        	int[] lists=new int[size];
        	for(int i=0;i<size;i++){
        		lists[i]=s.nextInt();
        	}
        	System.out.println(m.doSome(lists));
        }
	}
}

发表于 2017-06-04 20:51:52 回复(0)

Java

哈哈哈牛马

import java.util.ArrayList;
import java.util.Scanner;

/*
 *	QQ:	825580813(一起来敲代码)
 *	思路:
 *		1, 两个数为一个组合,所以要双重遍历数组.
 *		2, 如果两个数的最大公约数为1,则符合题目意思
 */
public class Main{
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n;
		while ((n = sc.nextInt()) != 0) {
			ArrayList<Integer> arr = new ArrayList<>();
			for (int i = 0; i < n; ++i) {
				arr.add(sc.nextInt());
			}
			
			int res = getFractionNum(arr);
			System.out.println(res);
		}
		sc.close();
	}

	private static int getFractionNum(ArrayList<Integer> arr) {
		int res = 0;
		for (int i = 0; i < arr.size(); ++i) {
			for (int j = i + 1; j < arr.size(); ++j) {
				if (gcd(arr.get(i), arr.get(j)) == 1) {
					res++;
				}
			}
		}
		return res;
	}

	private static int gcd(Integer num1, Integer num2) {
		return num1 == 0 ? num2 : gcd(num2 % num1, num1);
	}
	
}

发表于 2017-06-01 23:15:07 回复(0)