首页 > 试题广场 >

最简真分数

[编程题]最简真分数
  • 热度指数：17946 时间限制：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
算法知识视频讲解
添加回答
263保洁小妹头像 263保洁小妹
重点就是求最大公约数的函数 
#include <stdio.h>
#define N 600

int gcd(int a, int b)//欧几里得算法求最大公约数
{
    if(b==0) return a;
    else return gcd(b, a%b);
}

int main()
{
    int buf[N];
    int count, n;
    while(scanf("%d", &n)!=EOF)
    {
        for(int i=0; i<n; i++)
        {
            scanf("%d", &buf[i]);
        }
        count=0;//总计0个真分数
        for(int i=0; i<n; i++)//分母
        {
            for(int j=0; j<n; j++)//分子
            {
                if(i==j) continue;
                else if(buf[i]>buf[j] && gcd(buf[i], buf[j])==1)
                {
                    count++;
                }
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

发表于 2018-02-22 07:56:54 回复(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
TimeMac头像 TimeMac

看两个数有没有公约数

发表于 2018-10-08 23:50:19 回复(0)
Canopy头像 Canopy
请问下：为什么我这里用set将每个结果插入，最后set的大小比直接统计要少呢？
虽说set可以去重，但是这里每一对结果都是唯一的呀。
不懂，跪求大神解答 
 

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <string>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <functional>
#include <math.h>
#include <memory.h>
#include <utility>
using namespace std;



int GCD(int a,int b)
{
    if(a>b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
    while(b)
    {
        int t = a%b;
        a = b;
        b = t;
    }
    return a;
}
int A[610];

int main()
{
//	freopen("D:\\input.txt","r",stdin);
    int n;
    while(scanf("%d",&n)!=EOF)
    {
		if( n==0)break;
		set<pair<int,int> > S;
        for(int i = 0;i<n;i++)
        {
            scanf("%d",&A[i]);
        }
        sort(A,A+n);
        for(int i = 0;i<n;i++)
        {
            for(int j = i+1;j<n;j++)
            {
                if(GCD(A[i],A[j])==1)
                {
                    pair<int,int> P = pair<int,int>(A[i],A[j]);
                    S.insert(P);
                }
            }
        }
        printf("%d\n",S.size());
    }
}

发表于 2017-09-07 16:05:09 回复(5)
之一不之头像 之一不之
真分数是指分子小于分母的分数,最简真分数是指分子和分母没有共同公约数的分数。
所以只需要分母>分子且两者的公约数只有1时，满足题意 
#include<bits/stdc++.h>
using namespace std;

int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}

int main(){
    int n;
    while(cin>>n){
        if(n==0)break;
        int num[610];
        for(int i=0;i<n;i++){
            cin>>num[i];
        }
        int count=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j)continue;
                if(num[i]>num[j]&&(gcd(num[i],num[j])==1)){
                    count++;
                }
            }
        }
        cout<<count<<endl;
    }
    return 0;
}


发表于 2021-09-02 16:56:38 回复(0)
C/C++
拜托求求给一个offer头像 拜托求求给一个offer 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

vector<int> arr;

int GCD(int x, int y)
{
    if (y == 0)
    {
        return x;
    }
    else
    {
        return GCD(y, x % y);
    }
}

int main()
{
    int n, tmp, total;
    while (cin >> n)
    {
        if (n == 0)
        {
            break;
        }
        for (int i = 0; i < n; i++)
        {
            cin >> tmp;
            arr.push_back(tmp);
        }
        total = 0;
        for (int i = 0; i < arr.size(); i++) //分子
        {
            for (int j = 0; j < arr.size(); j++) //分母
            {
                if (arr[i] < arr[j] && GCD(arr[i], arr[j]) == 1)
                {
                    total++;
                }
            }
        }
        cout << total << endl;
        arr.clear();
    }
    return EXIT_SUCCESS;
}

发表于 2021-02-19 18:10:27 回复(0)
csyfZhang头像 csyfZhang
数论基础，辗转相除求余数
↑厚脸皮的把自己当年写的数论总结放上来
#include<iostream>
(720)#include<string>
#include<string.h>
(845)#include<vector>
#include<algorithm>
(831)#include<queue>
#include<cstdio>
(802)#include<set>
using namespace std;

#define MAX 605
(5423)#define ll int
#define inf 100000000

ll a[MAX];

int gcb(ll a, ll b) {
	if (b == 0)return a;
	return gcb(b, a%b);
}

int main() {
	ll n;
	while (cin >> n && n) {
		for (int i = 0; i < n; i++)cin >> a[i];
		sort(a, a + n); ll res = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (gcb(a[j], a[i]) == 1)res++;
			}
		}
		cout << res << endl;
	}
}


发表于 2020-04-20 21:11:57 回复(0)
C/C++
YhX.头像 YhX. 
#include<stdio.h>//有公约数则不行
int gongyue(int a,int b)//找是否存在公约数
{
    int i,j,min,key=1;
    min=a<b?a:b;
    for(i=2;i<=min;i++)
        if(a%i==0&&b%i==0)
        {//可以同时被整除  则为公约数
            key=0;break;//key=0代表有公约数
        }
    return key;
}
int main()
{
    int n,j,i,a[600],num=0;
    scanf("%d",&n);//输入
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
            if(gongyue(a[i],a[j]))//无公约数则个数加一
                num++;
    printf("%d",num);
}

发表于 2020-03-31 13:03:04 回复(1)
Java
LHC0512头像 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)
星期日伐头像 星期日伐 
#include<stdio.h>
int calmax(int a,int b)//计算最大公约数，辗转相除法
{
		return b==0? a:calmax(b,a%b);
}
main()
{
	int n;
	while(scanf("%d",&n)!=EOF&&n!=0)
	{
		int a[n];
		int i,j;
		int count=0;
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		for(i=0;i<n-1;i++)
		{
			for(j=i+1;j<n;j++)
			{
				if(calmax(a[j],a[i])==1)
					count++;
			}
		}
		printf("%d\n",count);
	}
}


发表于 2020-02-14 11:41:12 回复(3)
C/C++
fxzero头像 fxzero 
#include <stdio.h>
int main()
{
    short n,a[600],r,t1,t2,i,j;
    int sum;
    while(scanf("%hd",&n)!=EOF && n!=0)
    {
        sum=0;
        for(i=0;i<n;i++)scanf("%hd",&a[i]);
        for(i=0;i<n;i++)
            {
                for(j=i+1;j<n;j++)
                {
                    t1=(a[i]<a[j])?a[i]:a[j];
                    t2=(a[i]<a[j])?a[j]:a[i];
                    r=t1%t2;
                    while(r)                //辗转相除法
                    {
                        t1=t2;
                        t2=r;
                        r=t1%t2;
                    }
                    if(t2==1)sum++;
                }
            }
        printf("%d\n",sum);
    }
    return 0;
}

编辑于 2020-02-12 18:45:06 回复(0)
C/C++
妈妈桑茶道有三段头像 妈妈桑茶道有三段
1.最大公约数函数
2.排下序 
#include <bits/stdc++.h>
using namespace std;
int GCD(int a,int b)
{
    if(b==0)
        return a;
    else
        return GCD(b,a%b);
}
int main()
{
    int n;
    while(cin>>n&&n!=0)
    {
        int a[n];
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        sort(a,a+n);
        int count=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            {
                if(GCD(a[i],a[j])==1)
                    count++;
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

编辑于 2020-02-06 10:05:25 回复(0)
小陈也只是想要一个实习罢了头像 小陈也只是想要一个实习罢了 
//复杂度为o(n^2)，貌似先排一次序会降低一下复杂度
#include<iostream>
using namespace std;
int zdgy(int a,int b){
    while(a%b!=0){
        a=a-a/b*b;
        int temp=a;
        a=b;
        b=temp;
    }
    return b;
}
int main(){
    int n;
    while(cin>>n){
        if(n==0)
            break;
        int* a=new int[n];
        for(int i=0;i<n;i++)
            cin>>a[i];
        int count=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(a[i]>a[j]&&zdgy(a[i],a[j])==1)
                    count++;
                else if(a[i]<=a[j]&&zdgy(a[j],a[i])==1)
                    count++;
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

发表于 2020-01-11 22:40:12 回复(0)
C/C++
咖喱的cuy头像 咖喱的cuy

先排序，保证小的数字在前面
真分数的分子分母最大公因数为1
计算最大公因数：

gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = a

#include<algorithm>
using namespace std;

int num[600];

// gcd(a, b) = gcd(b, a % b)
// gcd(a, 0) = a
int gcd(int a, int b){
    if(b == 0){
        return a;
    }
    return gcd(b, a % b);
}

int main(){
    int n;
    while(cin >> n){
        int count = 0;
        for(int i = 0; i < n; i++){
            cin >> num[i];
        }
        sort(num, num + n);
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(gcd(num[i], num[j]) == 1){
                    count++;
                }
            }
        }
        cout << count << endl;
    }
    return 0;
}
发表于 2019-03-06 20:42:01 回复(2)
C/C++
_stormpang头像 _stormpang 
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 1000;

int num[maxn] = {0};

// 用于判断 r1 / r2 是否是最简真分数，如果是则他们的最大公约数为 1 ，且分子小于分母
int solve(int r1, int r2)
{
    int tmp;
    while(r1 != 0)
    {
        tmp = r1;
        r1 = r2 % r1;
        r2 = tmp;
    }
    if(r2 == 1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int main()
{
    int n;
    while(cin >> n)
    {
        if(n == 0)
        {
            break;
        }

        for(int i = 0; i < n; ++i)
        {
            cin >> num[i];
        }



        // 真分数一定是 分子小于分母 则先从小到大排序
        sort(num, num+n);

        int count = 0;      // 计数器

        for(int i = 0; i < n-1; ++i)
        {
            for(int j = i+1; j < n; ++j)
            {
                if(solve(num[i],num[j]) == 1)
                {
                    ++count;
                }
            }
        }
        cout << count << endl;

    }

    return 0;
}


发表于 2016-08-08 20:00:43 回复(0)
C/C++
随意凯头像 随意凯
大家可以帮忙看一下吗？我这程序问题出在while(scanf("%d",&n))问题上了，如果把这个换成cin>>n就没问题，否则运行超时，可以告诉我原因马？？？
#include<vector>
using namespace std;
int GCD(int x,int y){
    int temp;
    while(y!=0){
        temp=x%y;
        x=y;
        y=temp;
    }
    return x;
}
int main(){
    int n,count;
    int num[600];
    while(scanf("%d",&n)){
        if(n==0)    break;
        count=0;
        for(int i=0;i<n;i++)
            scanf("%d",&num[i]);
        for(int i=0;i<n-1;i++)
            for(int j=i+1;j<n;j++)
                if(GCD(num[i],num[j])==1)    count++;
        cout<<count<<endl;
    }
    return 0;
}
发表于 2020-03-08 11:41:26 回复(4)
C/C++
idutura头像 idutura 
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(b==0)return a;
    else return gcd(b,a%b);
}
int main(){
    int n;
    while(cin>>n){
       if(n==0) break;
        int temp[n];
        for(int i=0;i<n;i++){
            cin>>temp[i];
        }
        int sum = 0;
        for(int i=0;i<n;i++){ // 分子
            for(int j=0;j<n;j++){// 分母
                if(temp[i]>temp[j]) continue; // 分子大于分母，假分数，下一个
                else{
                    int d = gcd(temp[i],temp[j]);
                    if(d==1) sum++;
                }
            } 
        }
        cout<<sum<<endl;
    }
}

发表于 2020-03-03 17:41:30 回复(1)
狗and猫头像 狗and猫
#include <stdio.h>
using namespace std;

int GCD(int m,int n){
    if(n==0) return m;
    else return GCD(n,m%n);
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int input[1000];
        int count=0;
        for(int i=0;i<n;i++){
            scanf("%d",&input[i]);
        }
        if(input[0]==0) return 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(GCD(input[i],input[j])==1) count++;
            }
        }
        printf("%d\n",count/2);
    }
    return 0;
}
发表于 2025-01-24 23:27:33 回复(0)
guan09头像 guan09
***每组包含n（n<=600）和n个不同的整数，1/9有俩个281 281，**数据
编辑于 2025-01-12 15:36:00 回复(0)
牛客390280000号头像 牛客390280000号
#include <iostream>
using namespace std;

int gcd(int a,int b){//b小
    if(a%b==0){
        return b;
    }else{
        return gcd(b,a%b);
    }
}
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        if(n==0){
            break;
        }
        int buf[n];
        for(int i=0;i<n;i++){
            cin>>buf[i];
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(gcd(buf[j],buf[i])==1){
                    ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
}
// 64 位输出请用 printf("%lld")
编辑于 2024-03-27 21:38:05 回复(0)
提交观点

问题信息

穷举 基础数学
难度：
119条回答 11968浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最简真分数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号