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
6 8 798 10780Sample Output
No Solution 308 490
OJ-ID：
hdu-5974
author：
Caution_X
date of submission：
20191028
tags：
math
description modelling：
输入a,b，问是否存在x,y满足x+y=a && lcm(x,y)=b，若存在，输出一组(x,y)
major steps to solve it：
数论知识铺垫：
若i,j互质，则i+j和i*j互质
证明：
假设i,j互质但是i+j和i*j不互质，则(i+j)*k=i*j----①
两边同时%i得j*k%i=0,因为i，j互质，假如①能成立，你那么k%i一定为0
假设k%i=0，设k=m*i，k代入①得i*i*m+m*i*j=i*j，两边同时%j得到i*i*m%j=0
因为i，j互质，则m%j=0，设m=h*j (h>1)，则k=h*i*j
那么①：(i+j)*h*i*j=i*j => (i+j)*h=1，显然该等式不成立，即k%i=0不成立
又因为k%i=0不成立，所以(i+j)*k=i*j不成立，所以(i+j)和i*j互质。
本题分析：
设g=gcd(x,y)，i=x/g,j=y/g，
那么i*j*g=lcm(x,y)=b, (i+j)*g=a
因为i,j互质，则i+j和i*j互质，gcd(a,b)=gcd((i+j)*g,i*j*g)=g=gcd(x,y) => gcd(a,b)=gcd(x,y)---②
由x+y=a,lcm(x,y)=b,gcd(a,b)=gcd(x,y)三式联立求解一元二次方程即可
warnings：
输出的x,y满足x<y（题目没有明说）若输出结果为x,y，x,y符合条件但是x>y,会WA.
AC code:
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll x,ll y) { if(y == 0) return x; else return gcd(y,x%y); } ll big(ll a,ll b,ll l) { return a*b/l; } int main() { ll a,b; while(~scanf("%lld %lld",&a,&b)) { ll g = gcd(a,b); ll bb = a/g; bb = -bb; ll c = b/g; if(bb*bb>=4*c) { ll x = (ll)(-bb+sqrt(bb*bb-4*c))/2; ll y = -bb-x; ll xx = x*g; ll yy = y*g; if(xx>yy) swap(xx,yy); if(xx+yy == a && big(xx,yy,g) == b) printf("%lld %lld\n",xx,yy); else printf("No Solution\n"); } else printf("No Solution\n"); } return 0; }
HDU - 5974 A Simple Math Problem
原文：https://www.cnblogs.com/cautx/p/11755814.html