[编程题]Rational Sum (20)
- 热度指数：9027 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
Given N rational numbers in the form "numerator/denominator",
you are supposed to calculate their sum.
输入描述:
Each input file contains one test case. Each case starts with a positive integer N (<=100), followed in the next line N rational numbers "a1/b1 a2/b2 ..." where all the numerators and denominators are in the range of "long int". If there is a negative number, then the sign must appear in front of the numerator.
输出描述:
For each test case, output the sum in the simplest form "integer numerator/denominator" where "integer" is the integer part of the sum, "numerator" < "denominator", and the numerator and the denominator have no common factor. You must output only the fractional part if the integer part is 0.
示例1
输入
5 2/5 4/15 1/30 -2/60 8/3
输出
3 1/3
#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <string>
using namespace std;
typedef struct {
long numerator;
long denominator;
}Fraction;
int getLCM(int num1, int num2) { //求最小公倍数
int r;
if (num1 < num2) {
int temp = num1;
num1 = num2;
num2 = temp;
}
int m = num1;
int n = num2;
while ((r = m % n) != 0) {
m = n;
n = r;
}
return abs(num1 * num2 / n);
}
int getGCD(int num1, int num2) { //求最大公约数
int m, n, r;
if (num1 < num2) {
int temp = num1;
num1 = num2;
num2 = temp;
}
m = num1;
n = num2;
while((r = m % n) != 0) {
m = n;
n = r;
}
return abs(n);
}
int main() {
int count = 0;
cin >> count;
Fraction* data = (Fraction*)malloc(count * sizeof(Fraction));
for (int i = 0; i < count; i++) {
string input;
long num, deno;
cin >> input;
int separator = input.find('/');
string s_num = input.substr(0, separator);
string s_deno = input.substr(separator + 1);
num = atol(s_num.c_str());
deno = atol(s_deno.c_str());
data[i].numerator = num;
data[i].denominator = deno;
}
/*
for (int i = 0; i < count; i++) {
cout << i + 1 << ": " << data[i].numerator << "/" << data[i].denominator << endl;
}
*/
Fraction current = data[0];
for(int i = 1; i < count; i++) {
int LCM = getLCM(current.denominator, data[i].denominator);
int mulLeft = LCM / current.denominator;
int mulRight = LCM / data[i].denominator;
current.numerator = current.numerator * mulLeft + data[i].numerator * mulRight;
current.denominator = LCM;
}
//cout << "Result: " << current.numerator << "/" << current.denominator << endl;
if (current.numerator == 0) {
cout << 0 << endl;
return 0;
}
int GCD = getGCD(current.numerator, current.denominator);
current.numerator /= GCD;
current.denominator /= GCD;
int integer = 0;
if (current.numerator != 0) {
integer = current.numerator / current.denominator;
}
current.numerator %= current.denominator;
int flag;
if (current.numerator < 0) {
flag = -1;
} else if (current.numerator == 0){
flag = 0;
} else if (current.numerator > 0) {
flag = 1;
}
if (flag == -1) {
if (integer != 0)
cout << "-" << integer << " " << abs(current.numerator) << "/" << current.denominator << endl;
else
cout << "-" << abs(current.numerator) << "/" << current.denominator << endl;
} else if (flag == 1) {
if (integer != 0)
cout << integer << " " << current.numerator << "/" << current.denominator << endl;
else
cout << current.numerator << "/" << current.denominator << endl;
} else if (flag == 0) {
cout << integer << endl;
}
return 0;
}
发表于 2020-09-13 10:51:07
回复(0)
#include<cstdio>
#include<iostream>
using namespace std;
int n, a, b,c,d;
int gcd(int x, int y)
{
return y == 0 ? x : gcd(y, x%y);
}
int lcm(int x, int y)
{
return x / gcd(x, y)*y;
}
int main()
{
cin >> n;
scanf("%d/%d", &a, &b);
for (int i = 1; i < n; i++)
{
scanf("%d/%d", &c, &d);
int lc = lcm(b, d);
a = (lc / b*a + lc / d*c);
b = lc;
}
//cout << a << endl; cout << b << endl;
int tt = gcd(a, b);// cout << tt << endl;
a /= tt, b /= tt;
if (a!=0){
if ((a / b) != 0){
if ((a/b) > 0)
printf("%d %d/%d\n", a / b, a%b, b);
else
{
if ((a%b)!=0)
printf("%d %d/%d\n", a / b,-(a%b) , b);
else
printf("%d\n", a / b);
}
}
else{
if (a*b > 0){
printf("%d/%d\n", a, b);
}else
printf("-%d/%d\n", (a<0?-a:a),(b<0?-b:b));
}
}
else
printf("%d\n", a);
//cout << (-10 / 3) << endl; cout << (-10 % 3) << endl;
system("pause");
return 0;
}
发表于 2018-09-23 20:18:43
回复(0)
package go.jacob.day822;
import java.util.Scanner;
public class Demo1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String[] strs = new String[n];
//三个数分别为分子，分母，带分数的整数部分
int numerator = 0, denominator = 0, first = 0;
for (int i = 0; i < n; i++)
strs[i] = sc.next();
sc.close();
for (int i = 0; i < n; i++) {
int flag = 1, begin = 0;
if (strs[i].charAt(0) == '-') {
flag = -1;
begin = 1;
}
int tmpNumerator = flag * Integer.parseInt(strs[i].substring(begin, strs[i].indexOf("/")));
int tmpDenominator = Integer.parseInt(strs[i].substring(strs[i].indexOf("/") + 1));
if (tmpDenominator == 0)
return;
if (i == 0) {
numerator = tmpNumerator;
denominator = tmpDenominator;
} else {
numerator = numerator * tmpDenominator + tmpNumerator * denominator;
denominator *= tmpDenominator;
}
// 使用欧几里得算法求最大公约数，每次计算都要对分数进行化简，放置溢出
int factor = gcd(numerator, denominator);
if (factor == 0) {
System.out.println(0);
return;
}
numerator /= factor;
denominator /= factor;
}
// 把假分数化成带分数
first += numerator / denominator;
numerator = numerator % denominator;
// 输出结果的时候要判断：整数部分是否为0？分子书否为0？
if (first != 0)
if (numerator != 0)
System.out.println(first + " " + numerator + "/" + denominator);
else
System.out.println(first);
else if (numerator != 0)
System.out.println(numerator + "/" + denominator);
else
System.out.println(0);
}
private static int gcd(int a, int b) {
if (a == 0)
return 0;
if (a < 0)
a = -a;
if (b < 0)
b = -b;
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
if (a % b == 0)
return b;
else
return gcd(b, a % b);
}
}
发表于 2017-08-22 09:56:45
回复(0)
python solution，使用Fraction库，真简单。看了一下大家的解法，也就这个代码量最少了：
from fractions import Fraction
a,b,res=input(),input().split(),Fraction(0)
for i in b:
res+=Fraction(i)
if res.numerator<res.denominator:
print(res)
else:
aa=res.numerator//res.denominator
bb=res.numerator%res.denominator
print(str(aa)+" "+str(bb)+"/"+str(res.denominator))
编辑于 2017-10-09 09:45:51
回复(0)
#include<stdio.h>
long gcd(long a,long b){return !b?a:gcd(b,a%b);}
int main (){//the shorter,the better.
int n,i,f;long a,b,c,d,t;
for(;~scanf("%d",&n);a%b?a>b?printf("%ld %ld/%ld\n",f*a/b,a-a/b*b,b):printf("%ld/%ld\n",f*a,b):printf("%ld\n",f*a/b)){
for (a=i=0,b=1;i<n&&~scanf("%ld/%ld",&c,&d);a=a*d+b*c,b*=d,i++);
b>0?:(b*=-1,a*=-1),f=a>0?1:-1,a*=f,t=gcd(a,b),a/=t,b/=t;
}
}
发表于 2018-02-01 17:17:58
回复(0)
这其实就是一道小学数学题，貌似也没有什么快速的方法，就按照分数的加减法写了下代码。
读入数据，使用两个vector分别存储了对应分数的分子和分母，方便后面计算。
首先是进行通分，将分式通分为同分母的分式
然后再按同分母的分式加减，分母不变，分子相加减；
最后进行将假分数化为代分数，并进行约分。约分时求最小公约数可以使用辗转相除法计算。注意下负数的情况。
以下是完整代码：
#include<iostream>
#include<vector>
using namespace std;
//辗转相除法求最大公约数
int gcd(int x,int y)
{
int t;
while(y)
{
t=x%y;
x=y;
y=t;
}
return x;
}
int main()
{
int n;
cin >> n;
vector<long long> numerator(n); //存储分子部分
vector<long long> denominator(n); //存储分母部分
long long a, b;
char c;
long long product = 1; //各个数分母相乘的积
for (int i=0; i<n; i++)
{
cin >> a >> c >> b;
numerator[i] = a;
denominator[i] = b;
product *= b;
}
long long sum = 0;
for (int i=0; i<n; i++) //计算通分后分子相加的和
{
long long tmp = product/denominator[i] * numerator[i];
sum += tmp;
}
if (sum==0) //分子和为0，说明分数正负抵消，输出0
{
cout << 0;
return 0;
}
long long num = sum / product; //计算和是否为假分数
a = sum % product;
if (a == 0) //得到的和为整数
{
if (num != 0)
cout << num;
return 0;
}
long long g = gcd(product, a); //约分
a = a/g;
b = product/g;
if (b < 0) //处理负数的情况
{
a *= -1;
b *= -1;
}
if (num != 0)
cout << num << " ";
cout << a << "/" << b;
}
编辑于 2015-08-19 18:27:03
回复(0)
#include<iostream>
using namespace std;
//辗转相除法求最大公约数
int gcd(int x,int y){
int z;
while(y){
z = x % y;
x = y;
y = z;
}
return abs(x); //这里做了特殊处理，返回绝对值，因为公约数有可能是负数
}
int main(){
long a[2] = {0},b[2] = {0};
int n,gb;
cin>>n;
scanf("%ld/%ld",&a[1],&b[1]);
for(int i = 1;i < n;i++){
scanf("%ld/%ld",&a[0],&b[0]);
a[1] = a[0] * b[1] + a[1] * b[0];
b[1] = b[0] * b[1];
}
//先化为最简
gb = gcd(a[1],b[1]);
a[1] /= gb; b[1] /= gb;
//输出
if(a[1] == 0) cout<<0;
else if(a[1]/b[1] != 0 && a[1]%b[1] != 0){
cout<<a[1]/b[1]<<' '<<a[1]%b[1]<<'/'<<b[1];
}
else if(a[1]/b[1] != 0) cout<< a[1]/b[1];
else if(a[1] % b[1] != 0) cout<< a[1]%b[1]<<'/'<<b[1];
}
发表于 2020-03-05 23:02:10
回复(0)
有一说一，牛客网的测试用例更严格
import java.io.*;
import java.util.*;
import java.util.stream.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (br.readLine() != null) {
List<String> list = Arrays.asList(br.readLine().split(" "));
List<Long> numeratorList = list.stream()
.map(x -> Long.parseLong(x.split("/")[0]))
.collect(Collectors.toList());
List<Long> denominatorList = list.stream()
.map(x -> Long.parseLong(x.split("/")[1]))
.collect(Collectors.toList());
if (list.size() < 2) {
format(numeratorList.get(0), denominatorList.get(0));
continue;
}
long denominator = lcm(denominatorList);
long numerator = 0L;
for (int i = 0; i < list.size(); ++i) {
numerator += numeratorList.get(i) * (denominator / denominatorList.get(i));
}
format(numerator, denominator);
}
}
// 求最大公约数
private static long gcd(long a, long b) {
if (a < b) {
long tmp = a;
a = b;
b = tmp;
}
long c;
while ((c = (a % b)) != 0) {
a = b;
b = c;
}
return b;
}
// 求最小公倍数
private static long lcm(long a, long b) {
return (a * b) / gcd(a, b);
}
// 求一串数的最小公倍数
private static long lcm(List<Long> list) {
long start = lcm(list.get(0), list.get(1));
for (int i = 2; i < list.size(); ++i) {
start = lcm(start, list.get(i));
}
return start;
}
//分数简化，转换成结果，输出
private static void format(long numerator, long denominator) {
if (numerator == 0) { //整数和小数部分都为0的情况
System.out.println(0);
return;
}
long tmp = Math.abs(numerator);
long a = tmp / denominator;
long res = tmp - a * denominator;
if (res == 0) {
System.out.print(numerator / denominator);
return;
}
if (a != 0) {
System.out.format("%d ", a);
}
long gcdNum = gcd(res, denominator);
if (numerator < 0) {
res = -res;
}
System.out.format("%d/%d\n", res / gcdNum, denominator / gcdNum);
}
}
发表于 2025-01-09 23:54:31
回复(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct Fraction {
LL up,down;
} sum,temp;
LL gcd(LL a,LL b) {
return b==0?a:gcd(b,a%b);
}
Fraction reduction(Fraction a) {
if(a.down==-1) {
a.up=-a.up;
a.down=-a.down;
}
if(a.up==0) {
a.down=1;
} else {
LL d=gcd(abs(a.up),a.down);
a.up/=d;
a.down/=d;
}
return a;
}
Fraction Add(Fraction a,Fraction b) {
Fraction c;
c.up=a.up*b.down+a.down*b.up;
c.down=a.down*b.down;
return c;
}
void Printf(Fraction a) {
a=reduction(a);
if(a.down==1) {
cout<<a.up;
}
else if(abs(a.up)>a.down) {
cout<<a.up/a.down<<" "<<(a.up%a.down)<<'/'<<a.down;
}else{
cout<<a.up<<'/'<<a.down;
}
}
int main() {
int n;
cin>>n;
sum.up=0,sum.down=1;
for(int i=0;i<n;i++){
scanf("%lld/%lld",&temp.up,&temp.down);
sum=Add(sum,temp);
}
Printf(sum);
return 0;
}
发表于 2022-11-16 15:02:24
回复(1)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int lcm = 1, numerator, denominator; // 最小公倍数,分子,分母
List<Integer[]> numbers = new ArrayList<>();
for (int i = 0; i < n; i++) {
String[] split = sc.next().split("/");
numerator = Integer.parseInt(split[0]);
denominator = Integer.parseInt(split[1]);
numbers.add(new Integer[]{numerator, denominator});
lcm = (lcm * denominator) / gcd(lcm, denominator);
}
int sumNumerator = 0; // 求和
for (Integer[] number : numbers) sumNumerator += lcm / number[1] * number[0];
if (sumNumerator == 0) System.out.println(0);
else if(sumNumerator > 0){
int gcd = gcd(sumNumerator, lcm);
numerator = sumNumerator / gcd;
denominator = lcm / gcd;
int a = numerator / denominator;
int b = numerator % denominator;
if (a == 0) System.out.println(numerator + "/" + denominator);
else if (b == 0) System.out.println(a);
else System.out.println(a + " " + b + "/" + denominator);
} else {
sumNumerator=-sumNumerator;
int gcd = gcd(sumNumerator, lcm);
numerator = sumNumerator / gcd;
denominator = lcm / gcd;
int a = numerator / denominator;
int b = numerator % denominator;
if (a == 0) System.out.println(-numerator + "/" + denominator);
else if (b == 0) System.out.println(-a);
else System.out.println(-a + " " + b + "/" + denominator);
}
}
static int gcd(int a, int b) {
int t;
while (b != 0) {
t = b;
b = a % b;
a = t;
}
return a;
}
}
发表于 2022-10-31 19:42:56
回复(0)
#include<iostream>
#include<string>
#include<vector>
#include<stdlib.h>
#include<math.h>
using namespace std;
int gys(long ss,long mm){
//int m=abs(ss)*abs(mm);
if(ss<0){
ss*=-1;
}
if(mm<0){
mm*=-1;
}
/*long t;
if(mm<ss)
{
t=mm;
mm=ss;
ss=t;
}*/
int n=abs(mm)%abs(ss);
while(n!=0){
mm=ss;
ss=n;
n=mm%ss;
}
return ss;
}
int main(){
vector<long> s;
vector<long> m;
int count=0;
char son[100],mot[100];
string user;
string user_s[50];
string user_m[50];
int N;
cin>>N;
int n=N;
while(N){
//cin>>user;
cin>>user;
for(int i=0;i<user.size();i++){
if(user[i]=='/'){
int curr=0;
while(curr<i){
son[curr]=user[curr];
curr++;
}
son[curr]='\0';
s.push_back(atoi(son));
user_s[count]=(string)son;
curr=0;
i++;
while(i<user.size()){
mot[curr]=user[i];
i++;
curr++;
}
mot[curr]='\0';
m.push_back(atoi(mot));
user_m[count]=(string)mot;
count++;
break;
}
}
N--;
//s.push_back(user);
}
/*cout<<"当前输入的所有分子:";
for(int i=0;i<count;i++)
cout<<user_s[i]<<" ";
cout<<endl;
cout<<"当前输入的所有分母:";
for(i=0;i<count;i++)
cout<<user_m[i]<<" ";
cout<<endl;*/
long first,_first,flag;
long ss=s[0];
long mm=m[0];
for(int i=0;i<n;i++){
if(n-i>1){
ss=ss*m[i+1]+mm*s[i+1];
mm=mm*m[i+1];
}
}
// cout<<"当前的分子和为:"<<ss<<endl;
// cout<<"当前的分母和为:"<<mm<<endl;
first=abs(ss)/abs(mm);
_first=ss/mm;
if(ss<0){
ss+=first*mm;
if(ss==0){
flag=1;
}
}else{
ss-=first*mm;
}
if(ss!=0){
long mode=gys(ss,mm);
ss/=mode;
mm/=mode;
if(first!=0)
printf("%ld %ld/%ld",first,ss,mm);
else
printf("%ld/%ld",ss,mm);
}else{
if(flag=1)
cout<<_first;
else
cout<<0;
}
return 0;
}
#include<string>
#include<vector>
#include<stdlib.h>
#include<math.h>
using namespace std;
int gys(long ss,long mm){
//int m=abs(ss)*abs(mm);
if(ss<0){
ss*=-1;
}
if(mm<0){
mm*=-1;
}
/*long t;
if(mm<ss)
{
t=mm;
mm=ss;
ss=t;
}*/
int n=abs(mm)%abs(ss);
while(n!=0){
mm=ss;
ss=n;
n=mm%ss;
}
return ss;
}
int main(){
vector<long> s;
vector<long> m;
int count=0;
char son[100],mot[100];
string user;
string user_s[50];
string user_m[50];
int N;
cin>>N;
int n=N;
while(N){
//cin>>user;
cin>>user;
for(int i=0;i<user.size();i++){
if(user[i]=='/'){
int curr=0;
while(curr<i){
son[curr]=user[curr];
curr++;
}
son[curr]='\0';
s.push_back(atoi(son));
user_s[count]=(string)son;
curr=0;
i++;
while(i<user.size()){
mot[curr]=user[i];
i++;
curr++;
}
mot[curr]='\0';
m.push_back(atoi(mot));
user_m[count]=(string)mot;
count++;
break;
}
}
N--;
//s.push_back(user);
}
/*cout<<"当前输入的所有分子:";
for(int i=0;i<count;i++)
cout<<user_s[i]<<" ";
cout<<endl;
cout<<"当前输入的所有分母:";
for(i=0;i<count;i++)
cout<<user_m[i]<<" ";
cout<<endl;*/
long first,_first,flag;
long ss=s[0];
long mm=m[0];
for(int i=0;i<n;i++){
if(n-i>1){
ss=ss*m[i+1]+mm*s[i+1];
mm=mm*m[i+1];
}
}
// cout<<"当前的分子和为:"<<ss<<endl;
// cout<<"当前的分母和为:"<<mm<<endl;
first=abs(ss)/abs(mm);
_first=ss/mm;
if(ss<0){
ss+=first*mm;
if(ss==0){
flag=1;
}
}else{
ss-=first*mm;
}
if(ss!=0){
long mode=gys(ss,mm);
ss/=mode;
mm/=mode;
if(first!=0)
printf("%ld %ld/%ld",first,ss,mm);
else
printf("%ld/%ld",ss,mm);
}else{
if(flag=1)
cout<<_first;
else
cout<<0;
}
return 0;
}
发表于 2021-10-18 21:36:59
回复(0)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <vector>
#include <map>
#include <iomanip>
#include <sstream>
using namespace std;
//1081 Rational Sum (20分)
//化最简分式本质上就是找最大公约数
//pat.6，全为0时需要输出0
//pat与牛客均通过
int maxc(int a, int b) {
//获得最大公约数
int t;
while (b != 0) {
t = a % b;
a = b;
b = t;
}
return a;
}
int main() {
int n;
cin >> n;
long long x, y;
long long itg = 0, nu = 0, den = 1; //寄存的整数，分子，分母
string e;
long long p, mc;
for (int i = 0; i < n; ++i) {
cin >> e;
p = e.find('/');
x = stoll(e.substr(0, p)); //分子
y = stoll(e.substr(p+1)); //分母
//并入寄存部分
itg += x / y; //这样做一次可以避免分子溢出
x = x % y;
nu = nu * y + x * den;
den = den * y;
itg += nu / den; //相加后处理整数部分
nu = nu % den;
//约分
mc = nu < 0 ? maxc(-nu, den) : maxc(nu, den);
nu /= mc;
den /= mc;
}
if (itg != 0) {
cout << itg;
if (nu != 0) cout << " ";
}
if (nu != 0) {
cout << nu << "/" << den;
}
//pat.6，全为0时需要输出0
if (itg == 0 && nu == 0) cout << 0;
return 0;
}
编辑于 2020-02-29 16:16:19
回复(0)
using System;
using System.Collections.Generic;
using System.Collections.Generic;
namespace PAT_01
{
class Program
{
/*
题目描述
Given N rational numbers in the form "numerator/denominator", you are supposed to calculate their sum.
{
class Program
{
/*
题目描述
Given N rational numbers in the form "numerator/denominator", you are supposed to calculate their sum.
输入描述:
Each input file contains one test case. Each case starts with a positive integer N (<=100), followed in the next line N rational numbers "a1/b1 a2/b2 ..." where all the numerators and denominators are in the range of "long int". If there is a negative number, then the sign must appear in front of the numerator.
Each input file contains one test case. Each case starts with a positive integer N (<=100), followed in the next line N rational numbers "a1/b1 a2/b2 ..." where all the numerators and denominators are in the range of "long int". If there is a negative number, then the sign must appear in front of the numerator.
输出描述:
For each test case, output the sum in the simplest form "integer numerator/denominator" where "integer" is the integer part of the sum, "numerator" < "denominator", and the numerator and the denominator have no common factor. You must output only the fractional part if the integer part is 0.
输入例子:
5
2/5 4/15 1/30 -2/60 8/3
5
2/5 4/15 1/30 -2/60 8/3
输出例子:
3 1/3
*/
static void Main(string[] args)
{
var count = long.Parse(Console.ReadLine());
var molecularList = new List<long>();
var denominatorList = new List<long>();
foreach (var item in Console.ReadLine().Split(' '))
{
var str = item.Split('/');
if (str[0][0] == '-')
{
molecularList.Add(long.Parse(str[0].Remove(0, 1)) * -1);
}
else
{
molecularList.Add(long.Parse(str[0]));
}
denominatorList.Add(long.Parse(str[1]));
}
var maxMaleMultiple = denominatorList[0];
for (int index = 1; index < count; index++)
{
maxMaleMultiple = GetMaxMaleMultiple(maxMaleMultiple, denominatorList[index]);
}
3 1/3
*/
static void Main(string[] args)
{
var count = long.Parse(Console.ReadLine());
var molecularList = new List<long>();
var denominatorList = new List<long>();
foreach (var item in Console.ReadLine().Split(' '))
{
var str = item.Split('/');
if (str[0][0] == '-')
{
molecularList.Add(long.Parse(str[0].Remove(0, 1)) * -1);
}
else
{
molecularList.Add(long.Parse(str[0]));
}
denominatorList.Add(long.Parse(str[1]));
}
var maxMaleMultiple = denominatorList[0];
for (int index = 1; index < count; index++)
{
maxMaleMultiple = GetMaxMaleMultiple(maxMaleMultiple, denominatorList[index]);
}
long sum = 0;
for (int index = 0; index < count; index++)
{
sum += molecularList[index] * maxMaleMultiple / denominatorList[index];
}
{
sum += molecularList[index] * maxMaleMultiple / denominatorList[index];
}
var value = sum / maxMaleMultiple;
var maxC = GetMaxConventions(maxMaleMultiple, sum - (value * maxMaleMultiple));
Console.WriteLine("{0} {1}/{2}", value, (sum - (value * maxMaleMultiple)) / maxC, maxMaleMultiple / maxC);
}
var maxC = GetMaxConventions(maxMaleMultiple, sum - (value * maxMaleMultiple));
Console.WriteLine("{0} {1}/{2}", value, (sum - (value * maxMaleMultiple)) / maxC, maxMaleMultiple / maxC);
}
private static long GetMaxConventions(long a, long b)
{
long max = a > b ? a : b;
long min = a < b ? a : b;
while (max % min != 0)
{
a = min;
b = max % min;
max = a > b ? a : b;
min = a < b ? a : b;
}
return min;
}
{
long max = a > b ? a : b;
long min = a < b ? a : b;
while (max % min != 0)
{
a = min;
b = max % min;
max = a > b ? a : b;
min = a < b ? a : b;
}
return min;
}
private static long GetMaxMaleMultiple(long a, long b)
{
return a * b / GetMaxConventions(a, b);
}
{
return a * b / GetMaxConventions(a, b);
}
}
}
}
发表于 2019-08-23 11:16:18
回复(0)
#include
#include
#include
using namespace std;
int gys(int a,int b){return !b?a:gys(b,a%b);} //大的数字为负数，则返回负数
int main(){
int n,f; scanf("%d",&n);
int s1,s2; scanf("%d/%d",&s1,&s2);
for(int i=1;i<n;i++){
int t1,t2; scanf("%d/%d",&t1,&t2);
s1=s1*t2+t1*s2; s2=s2*t2; //先算s1后算s2，避免先改变s2
int t=gys(s2,s1);
s2/=t; s1/=t;
if(s2<0) s2*=-1,s1*=-1; //保证s2为正数
}
s1<0?f=-1,s1*=-1:f=1;
if(s1%s2==0){ //0%6,0/6 = 0
printf(f>0||!s1?"%d":"-%d",s1/s2);
}else{
if(s1/s2==0) printf(f>0?"%d/%d":"-%d/%d",s1,s2);
else printf(f>0?"%d %d/%d":"-%d %d/%d",s1/s2,s1%s2,s2);
}
return 0;
}
发表于 2019-02-24 14:30:24
回复(0)
/*
* ============================================================================================
*
* Filename: 1001 Public Bike Management (30).cpp
*
* Version: 1.0
* Created: 2018/09/25 13:06:07
* Revision: none
* Compiler: gcc
*
* Author: Covfefe
* Organization: Fs-studio
*
* Description:
*
* idea:
*
* ============================================================================================
*/
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
#define FOR(i,n) for(i = 0; i < n; i++)
int main()
{
int N, a[102], b[102], c = 0, d = 1; //long int将不能过测试点，但运行正确。。long long运行也不正确
int i, j, k, maxab;
cin >> N;
FOR(i, N)
scanf("%d/%d", &a[i], &b[i]);
if (N % 2 != 0) //若总个数为奇数
{
c = a[N - 1];
d = b[N - 1];
N--;
}
while (N > 1)
{
for (i = 0; i < N; i += 2)
{
a[i / 2] = a[i] * b[i + 1] + a[i + 1] * b[i];
b[i / 2] = b[i] * b[i + 1];
}
N /= 2;
}
a[0] = a[0] * d + c * b[0];
b[0] = b[0] * d;
maxab = a[0] > b[0] ? a[0] : b[0];
for(j = maxab; j >= 1; j--)
if (a[0] % j == 0 && b[0] % j == 0)
{
a[0] /= j;
b[0] /= j;
break;
}
if (!a[0])
{
cout << a[0];
}
else
{
if (abs(a[0]) > b[0])
{
cout << a[0] / b[0] << " ";
a[0] %= b[0];
}
if (a[0])
cout << a[0] << "/" << b[0];
}
return 0;
}
* ============================================================================================
*
* Filename: 1001 Public Bike Management (30).cpp
*
* Version: 1.0
* Created: 2018/09/25 13:06:07
* Revision: none
* Compiler: gcc
*
* Author: Covfefe
* Organization: Fs-studio
*
* Description:
*
* idea:
*
* ============================================================================================
*/
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
#define FOR(i,n) for(i = 0; i < n; i++)
int main()
{
int N, a[102], b[102], c = 0, d = 1; //long int将不能过测试点，但运行正确。。long long运行也不正确
int i, j, k, maxab;
cin >> N;
FOR(i, N)
scanf("%d/%d", &a[i], &b[i]);
if (N % 2 != 0) //若总个数为奇数
{
c = a[N - 1];
d = b[N - 1];
N--;
}
while (N > 1)
{
for (i = 0; i < N; i += 2)
{
a[i / 2] = a[i] * b[i + 1] + a[i + 1] * b[i];
b[i / 2] = b[i] * b[i + 1];
}
N /= 2;
}
a[0] = a[0] * d + c * b[0];
b[0] = b[0] * d;
maxab = a[0] > b[0] ? a[0] : b[0];
for(j = maxab; j >= 1; j--)
if (a[0] % j == 0 && b[0] % j == 0)
{
a[0] /= j;
b[0] /= j;
break;
}
if (!a[0])
{
cout << a[0];
}
else
{
if (abs(a[0]) > b[0])
{
cout << a[0] / b[0] << " ";
a[0] %= b[0];
}
if (a[0])
cout << a[0] << "/" << b[0];
}
return 0;
}
发表于 2018-10-17 23:38:57
回复(0)
有哪一位大神能告诉我我自己写的辗转相除法哪里错了，题目老是报浮点错误（可能除0）CommonDivisor(abs(sumA), abs(sumB));这个是我的函数
#include <iostream>
#include <math.h>
using namespace std;
long long CommonDivisor(long long a, long long b);
long long gcd(long long x,long long y);
int main()
{
int n;
cin >> n;
long long a,b;
long long sumA=0,sumB=1;
for(int i=0; i<n; i++)
{
scanf("%ld/%ld",&a,&b);
sumA=sumA*b+a*sumB;
sumB=b*sumB;
//long long commonDivisor = CommonDivisor(abs(sumA), abs(sumB));
long long commonDivisor = gcd((sumA < 0)?(-sumA):sumA, sumB);
if(CommonDivisor == 0)
cout << a << b <<endl;
sumA = sumA / commonDivisor;
sumB = sumB / commonDivisor;
}
long long master = sumA / sumB,y = sumA % sumB;
if(y==0){
cout << master << endl;
}
else
{
if(master)
{
cout << master << " ";
}
cout << y << "/" << sumB << endl;
}
}
long long gcd(long long x,long long y) {
return y?gcd(y, x % y):x;
}
long long CommonDivisor(long long a, long long b)
{
long long max=a>b?a:b;
long long min=a>b?b:a;
long long remainder = max%min;
if(min == 0)
cout << "fdafdsa" ;
long long remainder1 = 0;
while(remainder)
{
remainder1 = min % remainder;
//cout << "remainder is 0" << endl;
if(remainder1 != 0)
{
min = remainder;
remainder = remainder1;
}
else
{
break;
}
}
return remainder;
}
发表于 2018-07-25 17:36:48
回复(0)
问题信息
难度：
28条回答
18收藏
11542浏览
通过挑战的用户
-
2023-02-23 19:19:15
-
2023-02-21 14:47:58 -
2023-02-21 10:31:02 -
2023-02-18 16:51:20 -
2023-02-17 17:24:05
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
