最简真分数

[编程题]最简真分数

热度指数：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

算法知识视频讲解

Python

lx的流星

while True:
    try:
        n=int(input().strip())
        inp=sorted(list(map(int,input().strip().split(' '))))
        def iszhenfenshu(i,j):
            result=True
            if i!=j:
                if i==0:
                    result=False
                elif i>1:
                    while (j%i)!=0:
                        k=j%i
                        j=i
                        i=k
                    if i!=1:
                        result=False
            else:
                result=False
            return result
        num=0
        for i in range(n-1):
            for j in range(i+1,n):
                if iszhenfenshu(inp[i],inp[j]):
                    num+=1
        print(num)

    except:
        break

编辑于 2019-08-02 09:17:19 回复(0)

Python

TimeMac

看两个数有没有公约数

发表于 2018-10-08 23:50:19 回复(0)

Python

华科平凡

MMP,使用python3，连math库都不能引用，还得手写个***函数。

ac代码如下：

def ***(a,b):
    while b:
        a,b=b,a%b
    return a

while True:
    try:
        a,b,res=int(input()),list(map(int,input().split())),0
        for i in range(a-1):
            for j in range(i+1,a):
                if ***(b[i],b[j])==1:res+=1
        print(res)
    except:
        break

发表于 2017-10-06 14:08:11 回复(0)

Python

红尘梦断都城

def Is_Simple(m,n):
    while n:
        m, n = n, m%n
    return m
while 1:
    try:
        n=int(input())
        num=0
        s=list(map(int,input().split()))
        for i in range(len(s)):
            for j in range(i+1,len(s)):
                if Is_Simple(s[i],s[j])==1:
                    num+=1
        print(num)
    except:
        break

发表于 2017-09-04 14:25:36 回复(0)