专栏首页小樱的经验随笔HDU 2503 a/b + c/d(最大公约数与最小公倍数,板子题)

HDU 2503 a/b + c/d(最大公约数与最小公倍数,板子题)

话不多说,日常一水题,水水更健康!┗|`O′|┛ 嗷~~

a/b + c/d

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 14345    Accepted Submission(s): 7470

Problem Description

给你2个分数,求他们的和,并要求和为最简形式。

Input

输入首先包含一个正整数T(T<=1000),表示有T组测试数据,然后是T行数据,每行包含四个正整数a,b,c,d(0<a,b,c,d<1000),表示两个分数a/b 和 c/d。

Output

对于每组测试数据,输出两个整数e和f,表示a/b + c/d的最简化结果是e/f,每组输出占一行。

Sample Input

2

1 2 1 3

4 3 2 3

Sample Output

5 6

2 1

Source

《ACM程序设计》短学期考试_软件工程及其他专业

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2503

分析:就是求最大公约数与最小公倍数,概念详解请参看我的博客!

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int gcd(int a,int b)
 4 {
 5     return b==0?a:gcd(b,a%b);
 6 }
 7 int main()
 8 {
 9     int n;
10     while(scanf("%d",&n)!=EOF)
11     {
12         while(n--)
13         {
14             int a,b,c,d;
15             scanf("%d%d%d%d",&a,&b,&c,&d);
16             int t=gcd(b,d);//先求出两分母的最大公因式
17             int m=b*d/t;//求出两分母的最小公倍数
18             int k=m/b*a+m/d*c;//再计算两分子之和
19             int x=gcd(k,m);//新的分子与新的分母的比值,先得求出新分子与新分母的最大公因式
20             int q1=k/x;//求最简整数比,分别输出即可!
21             int q2=m/x;
22             printf("%d %d\n",q1,q2);//注意空格的输出
23         }
24     }
25     return 0;
26 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 详解斯坦纳点及斯坦纳树及模版归纳总结

    ①什么是斯坦纳点?   假设原来已经给定了个点,库朗等指出需要引进的点数至多为,此种点称为斯坦纳点。过每一斯坦纳点,至多有三条边通过。若为三条边,则它们两两交成...

    Angel_Kitty
  • 并查集(个人模版)

    并查集: 1 int find(int a) 2 { 3 int r=a; 4 while(f[r]!=r) 5 ...

    Angel_Kitty
  • 回溯算法入门及经典案例剖析(初学者必备宝典)

    前言 基于有需必写的原则,并且当前这个目录下的文章数量为0(都是因为我懒QAQ),作为开局第一篇文章,为初学者的入门文章,自然要把该说明的东西说明清楚,于是。。...

    Angel_Kitty
  • HDU 2196 Computer(树的直径)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2196

    Ch_Zaqdt
  • LOJ#2552. 「CTSC2018」假面(期望 背包)

    转移的时候若要淦这个人,那么\(f[i][j] = (f[i - 1][j] + 1) * p + (f[i - 1][j]) * (1 - p)\)

    attack
  • Leetcode 421. Maximum XOR of Two Numbers in an Array

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • CF910A The Way to Home SPFA(队列优化)

    一只青蛙现在在一个数轴上,它现在要从点 111 跳到点 nnn ,它每次可以向右跳不超过 ddd 个单位。比如,它可以从点 xxx 跳到点 x+ax+ax+a ...

    用户2965768
  • 【剑指Offer】51. 数组中的逆序对

    在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

    瑞新
  • 蓝桥杯 基础练习 数列排序

    第一行为一个整数n。 第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。

    Debug客栈
  • 【计算机本科补全计划】CCF计算机职业资格认证 2016-09 试题详解

    正文之前 我要东山再起了!!没错CCF迫在眉睫(其实是我以为报名之后一个月才考,结果报名截止之后一周就考试!(╯‵□′)╯︵┻━┻!!!还能好好做朋友吗!!)所...

    用户1687088

扫码关注云+社区

领取腾讯云代金券