2016/41届ACM/ICPC大连现场赛D题&hdoj5974_lwlldd的专栏-程序员宅基地

技术标签: ICPC  



A Simple Math Problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 697    Accepted Submission(s): 257


Problem Description

Given two positive integers a and b,find suitable X and Y to meet the conditions:
X+Y=a
Least Common Multiple (X, Y) =b
 

Input
Input includes multiple sets of test data.Each test data occupies one line,including two positive integers a(1��a��2*10^4),b(1��b��10^9),and their meanings are shown in the description.Contains most of the 12W test cases.
 

Output
For each set of input data,output a line of two integers,representing X, Y.If you cannot find such X and Y,output one line of "No Solution"(without quotation).
 

Sample Input
  
   
6 8
798 10780
 

Sample Output
  
   
No Solution
308 490
 

Source

解题思路:
数论题,用到的结论是若i,j互质,则i+j,i*j互质
x+y=a, lcm(x,y)=b, a b已知,求x,y是否存在,存在即按升序输出,不存在即输出 No Solution

因为lcm(x,y)=b,即 b=x*y/gcd(x,y)
1.a=x+y
2.b=x*y/gcd(x,y)
观察两个等式,只有先从gcd(x,y)入手看看
设gcd(x,y)=c
则 x可表示为 c*i
y可表示为c*j
(c显然分别x,y的因子,所以这样的表示是成立的)
同时 因为 c是x,y的最大公约数,则 i和j,显然是互质的(换句话说,如果i,j不互质,那么c就不是x,y的最大公约数)

因为 x=c*i ;
y=c*j
带入 a,b的等式:
a=c(i+j)
b=c * c *i *j /c=cij
那么可以得到 gcd(a,b)=gcd(c(i+j),cij)
根据数论定义,若i,j互质,则i+j,i*j互质
可知a,b公因子部分为c
gcd(a,b)=c=gcd(x,y)

这样显然:
1.a=x+y
2.b=x*y/gcd(x,y)=x * y/gcd(a,b)//a,b已给出,求个gcd即可

x=a-y
(a-y)y/gcd(a,b)=b,设gcd(a,b)=k

-y*y+ay-bk=0;

(系数都已知,根据求根公式,解一个一元二次方程即可)

题目要求整数解,
所以用解出来的跟、根,带入原来的两个等式验证是否成立,成立即输出解得的根,否则
No Solution

AC代码:

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long  LL;
LL gcd(LL a,LL b){
    return b?gcd(b,a%b):a;

}
int main(){
    long long  a,b,c,A,B;
    while(scanf("%I64d%I64d",&A,&B)!=EOF){
        LL g=gcd(A,B);

        a=-1;
        b=A;
        c=(-1)*(B*g);
        LL dlt=sqrt(b*b-4*a*c);
        LL x=-1*b+dlt;
        x=x/(2*a);    
        LL y=-1*b-dlt;
        y=y/(2*a);

        if(x+y==A)
        {
            if(x*y==B*g){
                LL t;
            if(a>b){
                t=a;
                a=b;
                b=t;

            }
            cout<<x<<" "<<y<<endl;
            }
            else
            {
            cout<<"No Solution"<<endl;    
            }
        }
        else
        cout<<"No Solution"<<endl;
    }



    return 0;
} 
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lwlldd/article/details/54234674

智能推荐

linux ls 外部命令,windows中使用linux ls命令_Skyline83的博客-程序员宅基地

习惯了linux下的ls命令,windows的dir用的很不习惯,又不想装cygwin, bash,就想把dir重命名为ls,发现dos下有个命令doskey可以完成该功能。在命令提示符下敲:&gt;doskey ls=dir然后再敲ls就可以列出文件了。当然,这个别名只是临时的,为了是它永久发挥作用,可以写一个bash.bat:doskey ls=dircmd要启动命令行时双击该文件就可以了。d...

使用ctags+vim工具察看源代码_DC00910的博客-程序员宅基地

//前提已安装ctags1、创建tags文件===========================================在要检索的源代码目录下创建ctags文件假设目录为/home/linux-4.0/$>cd /home/linux-4.0/$>ctags -R命令执行完毕后,会在目录下生成一个名为tags的文件2、设置vim配置文件

java 去除样式_JAVA去掉HTMl以及CSS样式_weixin_39671621的博客-程序员宅基地

public String delHTMLTag(String htmlStr) {String regEx_style = "]*?>[\s\S]*?"; //定义style的正则表达式String regEx_html = "]+>"; //定义HTML标签的正则表达式Pattern p_style = Pattern.compile(regEx_style, Pattern.CASE_INS...

jmeter测java模拟器_测试了5款最常见的模拟器,发现与Airtest自动化最配的竟然是......_王瑞恩的博客-程序员宅基地

前言模拟器是我们的测试小伙伴非常喜欢的一款工具。在使用airtest框架做自动化测试的时候,小伙伴们也是非常喜欢用模拟器来作为测试设备的,但是我们也收到过很多关于连接模拟器的问题:①airtest连不上xx模拟器怎么办② xx模拟器连上了但是好卡啊③ 哪款模拟器好用,有没有推荐的呀......别急,今天我们就用AirtestIDE来连接下5家主流的模拟器,看看这几款模拟器,到底谁好用一些。准备工作...

SEO优化常用的网络营销方式都有哪些_老齐SEO的博客-程序员宅基地

随着科学技术的发展,人们收入水平的提高,生产能力的提升,产品日趋多元化,为居民提供了更加丰富的选择。那么,在这个竞争激烈的时代,任何的产品事物都需要紧跟时代的步伐。产品的营销同样如此,在互联网快速发展的今天,如果企业不抓住线上的潜在用户,必死无疑。接下来为大家整理了SEO优化常用的网络营销方式。SEO优化常用的网络营销方式都有哪些1、搜索引擎营销即搜索引擎优化,是通过对网站结 构(内部链接结...

html怎么在td中加风格,html中如何让td里面的文字_Agnes 陳老師的博客-程序员宅基地

公告: 为响应国家净网行动,部分内容已经删除,感谢读者理解。话题:html中如何让td里面的文字问题详情:td height=40 colspan=2 align=centerstrong class=f14&amp;lt回答:给table加个id,如:table width="200" border="1" id="result" 然后遍历其下的所有td,替换字符,写一个函数,让他在页面载入完成...

随便推点

决策树,状态机等模型的本质意义。_NightPoetry的博客-程序员宅基地_决策树和状态机

原文:https://blog.csdn.net/gao7009/article/details/80221163模型的本质意义是为了模式化逻辑,使得复杂问题简单化,同时尽可能的实现代码复用以及尽可能高的可扩展行。根据“敏捷开发原则”因此如果你用上这些模型之后反而逻辑不畅请换个模型,其次不要跟一个模型较真,模型具有局限性,当遇到有局限性部分的模型,当场隔离出来换个模型并将他们组合起来发挥作用。其次,代码的本质就是条件和动作。所以无论什么模型都可以做成并行的一连串的if语句,甚至都不用进行if嵌套。我

oracle索引对增删改查的影响,Oracle索引 主键影响查询速度_丛乐的博客-程序员宅基地

要提高查询速度,一般:1.不需要删除的字段,建主键;有可能要被删除的字段,建索引。2.假如一次提交5W个号码,每个都要和数据库里90W号码进行比较5W个号码中哪些号码是90W号码中的。那么将90W号码建一个表,一个字段就是号码字段,然后把该字段设为主键即可。update前100条为0,另外一个程序找状态为0的,要提高速度,要将这100条(所有条)的ID建索引。3.不管对什么字段建的什么索引,该字段...

SpringBoot:Spring容器的启动过程_weixin_30275415的博客-程序员宅基地

一、简述Spring的启动过程就是IoC容器的启动过程,本质上就是创建和初始化Bean的工厂(BeanFactory),BeanFactory是整个SpringIoC的核心,Spring使用BeanFactory来实例化、配置和管理Bean。二、SpringBoot的启动过程在SpringBoot中,SpringApplication封装了一套Spring应用的启动流程,对用...

mysql无法找到事件id100描述_MySQL错误is marked as crashed and last (automatic?) repair failed..._weixin_39791653的博客-程序员宅基地

MySQL运行久了,可能索引就会有问题,用navicat 可以非常方便的进行修复。事件 ID ( 100 )的描述(在资源( MySQL )中)无法找到。本地计算机可能没有必要的注册信息或消息 DLL 文件来从远程计算机显示消息。您可能可以使用 /AUXSOURCE= 标识来检索词描述;查看帮助和支持以了解详细信息。下列信息是事件的一部分:Fatal error: Can’t open and ...

jenkins 项目启动日志_如何实现类似“jenkins”的滚动日志功能?_贾扬清的博客-程序员宅基地

本文实现了一个类似jenkins滚动日志的小功能,如果你正在做发布系统类似的东西,这个功能会非常有用。滚动日志jenkins的日志能够滚动显示,关闭后重新进入依然能够继续滚动,非常棒。做这种效果,直接想到的有两种方式:1)Websocket2)轮询获取可是我太笨了,websocket代码对我来说有点复杂。另外我还没想清楚如果关了日志窗口重新进入,ws会有什么样的反应。所以我们还是轮询吧。通过c...

计算机应用后期影音制作,影音制作工具(ImTOO Movie Maker)_weixin_39885166的博客-程序员宅基地

ImTOO Movie Maker是一款影音制作工具,可以帮助用户从视频中快速创建高清质量和标准清晰度的电影,这样就可以在流行的设备上分享您的创作。有需要的小伙伴欢迎来西西下载体验。软件特色:以AVI、MPEG-1/2/4、DivX、XviD、ASF、MOV、RM、WMV格式输出电影,以便在iPod、iPhone、psP、PS3、Zune、Xbox、Wii和DS等设备上播放。通过电影制作软件,您可...

推荐文章

热门文章

相关标签