题解 - 南师大算法竞赛域

2

24220144郭荣圣 (小趴菜) LV 9 @ 2023-08-12 19:37:53

#include <iostream>
using namespace std;

int main(){
int n;
cin>>n;
int a[n],b[n];
cin>>b[0]>>a[0]>>b[1]>>a[1];
int c1,d1,c2,d2;
c1=a[0]*a[1];
d1=a[0]*b[1]+a[1]*b[0];
for(int i=2;i<n;i++){
cin>>b[i]>>a[i];
c2=c1*a[i];
d2=c1*b[i]+d1*a[i];
c1=c2;
d1=d2;
}
int min;
min = c1<d1 ? c1 : d1;
int i=2;
while(i<=min){
if(c1%i==0 && d1%i==0){
c1/=i;
d1/=i;
min/=i;
i=2;
}else i++;
}
cout<<d1<<" "<<c1;
return 0;
}

1

19230217阳 (19230217) LV 7 @ 2023-12-26 15:02:13

#include<iostream>
using namespace std;
struct Fraction {
int up, down;
};

Fraction add(Fraction f1, Fraction f2)
{
Fraction ret;
ret.up = f1.up * f2.down + f2.up * f1.down;
ret.down = f1.down * f2.down;
return ret;
}
int gcd(int a, int b)
{
//求大公因数
if (b == 0)return a;
else return gcd(b, a % b);
}
int main()
{
int n; cin >> n;
int i = 0;
Fraction f[100];
for(;i<2;i++)
{
cin >> f[i].up >> f[i].down;
}
Fraction ret=add(f[0], f[1]);
for (int i = 2; i < n; i++)
{
cin >> f[i].up >> f[i].down;
ret = add(ret, f[i]);
}
//cout << ret.up << " " << ret.down;未约分
int yue = gcd(ret.up, ret.down);
cout << ret.up/yue << " " << ret.down/yue;
}

1

幻♂想♂乡 (njnu19180319) LV 8 @ 2019-10-17 19:51:41

#include<iostream>
using namespace std;

struct Node
{
    int fen_zi;
    int fen_mu;
    Node *next;
};

class LinkList
{
private:
    int n;
    Node *head;
    Node *tail;
public:
    LinkList(int set_n)
    {
        n=set_n;
        head=NULL;
        tail=NULL;
    }

    void set_list(LinkList &L)
    {
        int x,y;
        for(int i=0;i<L.n;i++)
        {
            cin>>x>>y;
            L.insert(x,y);
        }
    }

    void insert(int x,int y)
    {
        Node *newp=new Node;
        newp->fen_zi=x;
        newp->fen_mu=y;
        if(head==NULL)
        {
            head=newp;
            tail=newp;
        }
        else
        {
            tail->next=newp;
            tail=newp;
        }
        if(tail!=NULL)
            tail->next=NULL;
    }

    int get_fen_mu()//得到不化简的分子
    {
        Node *p=head;
        int sum=1;
        while(p!=NULL)
        {
            sum=sum*p->fen_mu;
            p=p->next;
        }
        return sum;
    }

    int get_fen_zi(LinkList &L)//得到不化简的分母
    {
        Node *p=L.head;
        int sum=0;
        while(p!=NULL)
        {
            sum=sum+p->fen_zi*L.get_fen_mu()/p->fen_mu;
            p=p->next;
        }
        return sum;
    }

    int yue_shu(int x,int y)//求最大公约数
    {
        int tmp;
        if(x<y)
        {
            tmp=x;
            x=y;
            y=tmp;
        }
        return y==0?x:yue_shu(y,x%y);
    }
        
};

int main()
{
    int n;
    cin>>n;
    LinkList start(0);
    LinkList List(n);
    start.set_list(List);
    int x,y;
    x=start.get_fen_zi(List)/List.yue_shu(start.get_fen_zi(List),List.get_fen_mu());
    y=List.get_fen_mu()/List.yue_shu(start.get_fen_zi(List),List.get_fen_mu());
    cout<<x<<" "<<y<<endl;

    system("pause");
    return 0;
}

njnu19180319 @ 2019-10-17 19:52:07

链表才是斯巴拉西

0

19220448 董文杰 (董文杰) LV 9 @ 2023-05-18 10:07:53

import math

n = int(input())
up = 0
low = 1
for i in range(n):
    a, b = map(int, input().split())
    up = up * b + low * a
    low *= b
div = math.gcd(up, low)
up, low = up // div, low // div
print(up, low)

0

Xiaojian_Chen (小健391) LV 8 MOD @ 2019-11-19 14:24:32

#include <stdio.h>//多个分数相加

int fenmu(int b[],int n);

int simplify(int m,int s);

int main()

{

int n,i,c,d;

scanf("%d",&n);

int a[n],b[n],q[n],w[n];

for(i=0;i<n;i++)

scanf("%d%d",&a[i],&b[i]);

for(i=0;i<n;i++)//安置替身

{

q[i]=a[i];

w[i]=b[i];

}

c=fenmu(b,n);//c为分母

d=0; //d为分子

for(i=0;i<n;i++)

d=d+c/w[i]*q[i]; //注意此时a[],b[]的值因函数操作而改变，故要用替身
simplify(d,c);
return 0;

}

int fenmu(int b[],int n)

{

int i,j,r,c,d;
int a[n];//子函数定义与主函数同名数组对的
d=1;
for(i=0;i<n;i++)//安置替身
a[i]=b[i];
for(i=0;i<n-1;i++)
{

for(j=1;j<=b[i]&&j<=b[i+1];j++)

if(b[i]%j==0&&b[i+1]%j==0)

r=j;

b[i+1]=r;

}
for(i=0;i<n;i++)
d=d*a[i];
c=d/b[n-1];

return c;

}

int simplify(int m,int s)

{

int i,j;

for(i=1;i<=m&&i<=s;i++)

if(m%i==0&&s%i==0)

j=i;

printf("%d %d",m/j,s/j);//分数约分

}

-1

齐硕 LV 10 @ 2022-08-08 15:32:52

#include<iostream>
using namespace std;

struct Node
{
int fen_zi;
int fen_mu;
Node *next;
};

class LinkList
{
private:
int n;
Node *head;
Node *tail;
public:
LinkList(int set_n)
{
n=set_n;
head=NULL;
tail=NULL;
}

void set_list(LinkList &L)
{
int x,y;
for(int i=0;i<L.n;i++)
{
cin>>x>>y;
L.insert(x,y);
}
}

void insert(int x,int y)
{
Node *newp=new Node;
newp->fen_zi=x;
newp->fen_mu=y;
if(head==NULL)
{
head=newp;
tail=newp;
}
else
{
tail->next=newp;
tail=newp;
}
if(tail!=NULL)
tail->next=NULL;
}

int get_fen_mu()//得到不化简的分子
{
Node *p=head;
int sum=1;
while(p!=NULL)
{
sum=sum*p->fen_mu;
p=p->next;
}
return sum;
}

int get_fen_zi(LinkList &L)//得到不化简的分母
{
Node *p=L.head;
int sum=0;
while(p!=NULL)
{
sum=sum+p->fen_zi*L.get_fen_mu()/p->fen_mu;
p=p->next;
}
return sum;
}

int yue_shu(int x,int y)//求最大公约数
{
int tmp;
if(x<y)
{
tmp=x;
x=y;
y=tmp;
}
return y==0?x:yue_shu(y,x%y);
}

};

int main()
{
int n;
cin>>n;
LinkList start(0);
LinkList List(n);
start.set_list(List);
int x,y;
x=start.get_fen_zi(List)/List.yue_shu(start.get_fen_zi(List),List.get_fen_mu());
y=List.get_fen_mu()/List.yue_shu(start.get_fen_zi(List),List.get_fen_mu());
cout<<x<<" "<<y<<endl;
return 0;
}

-1

张任飞@汾湖实验初中 (JerryZRF) LV 8 @ 2021-02-03 16:22:00

#include<iostream>
using namespace std;

int * add(int z1, int m1, int z2, int m2);
int gcd(int a, int b);
int lcm(int a, int b);
int * huajian(int x[2]);

int main()
{
    int n;    //n个分数
    cin>>n;
    int z1, m1, z2, m2;    //分子 分母
    cin>>z1>>m1>>z2>>m2;
    int * sum = add(z1, m1, z2, m2);
    for(int i = 2; i < n; i++)
    {
        cin>>z2>>m2;
        sum = add(sum[0], sum[1], z2, m2);
    }
    if(sum[0] % sum[1] == 0)
    {
        cout<<sum[0] / sum[1];
        return 0;
    }
    sum = huajian(sum);
    cout<<sum[0]<<" "<<sum[1];
    return 0;
}

int * add(int z1, int m1, int z2, int m2)
{
    static int sum[2];      //返回结果
    int l = lcm(m1, m2);    //分母最小公倍数  新的分母
    int chen1 = l / m1;     //分母扩大的倍数 = 分子要扩大的倍数(z1, m1)
    int chen2 = l / m2;     //分母扩大的倍数 = 分子要扩大的倍数(z2, m2)
    z1 = z1 * chen1;        //扩大分子(z1)  新的分子(z1)
    z2 = z2 * chen2;        //扩大分子(z2)  新的分子(z2)
    int z = z1 + z2;        //分子之和  最后的分子
    sum[0] = z;    //分母
    sum[1] = l;    //分子
    return sum;    //分数
}

int gcd(int a, int b)    //辗转相除法
{
    while(1)
    {
        int r = a % b;
        if(r == 0)
            return b;
        a = b;
        b = r;
    }
}

int lcm(int a, int b)    //[a, b] = a * b / (a, b)
{
    return a * b / gcd(a, b);
}

int * huajian(int x[2])
{
    static int a[2];    //结果
    int g = gcd(x[0], x[1]);    //分母、分子最大公因数
    a[0] = x[0] / g;
    a[1] = x[1] / g;
    return a;
}

-1

njnu19180323 LV 7 @ 2019-10-07 02:10:44

#include <iostream>
using namespace std;
int MaxYue(int a,int b);
int MinBei(int a,int b);
int MaxYue(int a,int b)
{
    int tmp;
    if(a<b)   //如果a小于b，则交换值
    {
        tmp=a;
        a=b;
        b=tmp;
    }
    return b==0?a:MaxYue(b,a%b);  //运用辗转相除法求出最大公约数
}
int MinBei(int a,int b)
{
    return a*b/MaxYue(a,b);  //最小公倍数等于两数乘积除以最大公约数
}
int main()
{
    int i,n,a[1000],b[1000],asum=0,bsum;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i]>>b[i];
    if(n==1)  //如果只有一项，直接输出
    {
        i=MaxYue(a[0],b[0]);
        a[0]/=i;
        b[0]/=i;
        cout<<a[0]<<" "<<b[0];
        return 0;
    }
    bsum=MinBei(b[0],b[1]); //首先记录前两项分母的最小公倍数
    for(i=2;i<n;i++)
        bsum=MinBei(bsum,b[i]); //循环记录与后一个分母的最小公倍数
    for(i=0;i<n;i++)
        asum+=a[i]*bsum/b[i];  //分子乘以分母扩大的倍数然后相加
    i=MaxYue(asum,bsum);  //分子和分母进行约分，除以最大公倍数
    asum/=i;
    bsum/=i;  
    cout<<asum<<" "<<bsum;
    return 0;
}

题解

8 条题解

A6-3 最大公约数专题：多个分数的加法

信息

状态

开发

支持

题解

8 条题解

A6-3 最大公约数专题：多个分数的加法

信息

状态

开发

支持

还没有账户？

登录