首页 > 代码库 > Solve Equation gcd(x,y)=gcd(x+y,lcm(x,y)) gcd(x,y)=1 => gcd(x*y,x+y)=1
Solve Equation gcd(x,y)=gcd(x+y,lcm(x,y)) gcd(x,y)=1 => gcd(x*y,x+y)=1
/** 题目:Solve Equation 链接:http://acm.hnust.edu.cn/JudgeOnline/problem.php?id=1643 //最终来源neu oj 2014新生选拔赛题 题意:给定两个数的和以及他们的最小公倍数,求这两个数。 思路: x+y=A lcm(x,y)=B => x*y/gcd(x,y)=B 要把这两个公式联立,那么必须消掉gcd; 设:d = gcd(x,y), x = kx*d, y = ky*d; kx与ky互质; x+y=A => d(kx+ky)=A x*y/gcd(x,y)=B => d*kx*ky=B 由于kx与ky互质,所以kx*ky与(kx+ky)互质,那么d的大小为gcd(A,B); 那么: x+y=A x*y/gcd(A,B)=B; 联立两个式子判断是否可以获得整数解再解方程即可。 得出结论:gcd(x,y) = gcd(A,B) = gcd(x+y,lcm(x,y)); 一元二次方程解 b*b-4*a*c>=0有解。 x1 = (-b+sqrt(b*b-4*a*c))/(2*a); x2 = (-b-sqrt(b*b-4*a*c))/(2*a); 要判断是否是整数解,则要对分母对分子取余为0,以及开根号后为整数值。 */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const int maxn = 1000100; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } int main() { ll A, B; while(scanf("%lld%lld",&A,&B)==2) { ll d = gcd(A,B); ll deta = A*A-4*d*B; ll p = sqrt(deta+0.00001); if(p*p!=deta){ printf("No answer\n"); }else { if((A+p)%2!=0){ printf("No answer\n"); }else { ll x = (A-p)/2; ll y = (A+p)/2; printf("%lld %lld\n",x,y); } } } return 0; }
Solve Equation gcd(x,y)=gcd(x+y,lcm(x,y)) gcd(x,y)=1 => gcd(x*y,x+y)=1
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。