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

看两个数有没有公约数

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

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

#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

数论基础，辗转相除求余数

https://blog.csdn.net/csyifanZhang/article/details/104522039

↑厚脸皮的把自己当年写的数论总结放上来

#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.

#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

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

#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

先排序，保证小的数字在前面
真分数的分子分母最大公因数为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

#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<iostream>

#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

#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)

牛客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)

Python3

chong_0428

def gcd(a, b):#欧几里得算法求最大公约数
    if b==0:
        return a
    else:
        return gcd(b, a%b)

def fenshu(s):
    k=0
    for i in range(len(s)-1):
        for j in range(i+1, len(s)):
            if gcd(s[i], s[j]) == 1:
                k+=1
    return k


while True:
    try:
        n = int(input())
        a = list(map(int, input().split()))
        print(fenshu(a))
    except:
        break

编辑于 2024-03-11 12:08:01 回复(0)

C++

无问西东gmy

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int>arr(n);
        for (auto& i : arr) {
            cin >> i;
        }
        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) { //gcd为求最大公约数的函数
                    count++;
                }
            }
        }
        cout << count << endl;
    }
    return 0;
}

发表于 2024-01-30 15:17:17 回复(0)

最简真分数

输入描述:

输出描述:

输入

输出

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

ac代码如下：

问题信息

热门推荐

通过挑战的用户

相关试题