7828:最大公约数与最小公倍数

7828:最大公约数与最小公倍数

总时间限制: 1000ms 内存限制: 65536kB描述

两个正整数的最大公约数是G,最小公倍数是L,它们的和最小是多少?

输入两个不大于10000的正整数G和L,中间用单个空格隔开。数据保证L是G的倍数。输出一个正整数,即最小的和。样例输入

14 280

样例输出

126

来源《奥数典型题举一反三(小学五年级)》 (ISBN 978-7-5445-2882-5) 模拟试卷一 第6题

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int minx,a,b,x,y;
 4 int gcd(int x,int y) {
 5     if(y==0)return x;
 6     return gcd(y,x%y);
 7 }
 8 int lcm(int x,int y) {
 9     return x*y/gcd(x,y);
10 }
11 int main() {
12     cin>>x>>y;
13     minx=1000000;
14     for(int a=x; a<=y; a=a+x) 
15     {
16         if(x*y%a!=0)continue;
17         b=x*y/a;
18         if(gcd(a,b)==x&&lcm(a,b)==y)
19             if(a+b<minx)minx=a+b;
20     }
21     cout<<minx;
22     return 0;
23 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P1789 【Mc生存】插火把

题目背景 初一党应该都知道...... 题目描述 话说有一天linyorson在Mc开了一个超平坦世界,他把这个世界看成一个n*n的方阵,现在他有m个火把和k个...

3525
来自专栏数据结构与算法

洛谷P1730 最小密度路径(floyd)

很显然的一个dp方程\(f[i][j][k][l]\)表示从\(i\)到\(j\)经过了\(k\)条边的最小权值

893
来自专栏小樱的经验随笔

Gym 100952C&&2015 HIAST Collegiate Programming Contest C. Palindrome Again !!【字符串,模拟】

C. Palindrome Again !! time limit per test:1 second memory limit per test:64 meg...

2633
来自专栏落影的专栏

程序员进阶之算法练习(二)

前言 看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。 A 题目链接 题目大意:n个点,坐标x[i]从小到大,每个点可以选择Le...

2946
来自专栏聊聊技术

原 初学算法-分治法求平面上最近点对(Cl

54615
来自专栏java一日一条

Java8 HashMap实现原理探究

前言:Java8之后新增挺多新东西,在网上找了些相关资料,关于HashMap在自己被血虐之后痛定思痛决定整理一下相关知识方便自己看。图和有些内容参考的这个文章:...

1372
来自专栏蜉蝣禅修之道

Python递归求矩阵的行列式

2074
来自专栏数据小魔方

作图前的数据预处理

今天给大家讲解作图前原数据的排序整理技巧! 前一篇推送讲到了条形图数据系列顺序反转问题 原数据系列的排序只是给大家提示要用智能表格排序 今天交给大家一种更简洁...

2647
来自专栏小樱的经验随笔

浅谈String模块ascii_letters和digits

本文介绍string模块ascii_letters和digits方法,其中ascii_letters是生成所有字母,从a-z和A-Z,digits是生成所有数字...

4017
来自专栏tkokof 的技术,小趣及杂念

HGE系列之五 管中窥豹(基础类别)

继上次我们编写了那个小程序之后,想必大家对于HGE的认识都有了进一步的提高,那么现在,我想则是时候来一番“管中窥豹”,睹一睹HGE的源码实现了 :)而相应的源...

951

扫码关注云+社区