题目链接
题目大意
给你\(a(1<=a<=2e4),b\)(1<=b<=1e9)
要你找到x和y使得\(x+y=a,lcm(x,y)=b\)
题目思路
这个主要是要明白
\(gcd(x,y)=gcd(a,b)\)
设\(x=nk,y=mk\)
则\(gcd(a,b)=gcd((n+m)k,nmk)\)
而\(gcd(n,m)=1\)推到出\(gcd(n+m,nm)=1\)
\(xy=lcm(x,y)*gcd(x,y)=b*gcd(a,b)\)
而已知\(x+y=a\)
则可以推出x和y
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e2+5,inf=0x3f3f3f3f,mod=1e9+7;
const int eps=1e-3;
int a,b;
signed main(){
while(scanf("%d%d",&a,&b)!=-1){
bool flag;
int mul=__gcd(a,b)*b,x,y;
if(a*a-4*mul<0){
flag=0;
}else{
int cha=sqrt(a*a-4*mul);
x=(cha+a)/2;
y=(a-cha)/2;
if(x+y==a&&x/__gcd(x,y)*y==b){
flag=1;
}else{
flag=0;
}
}
if(!flag){
printf("No Solution\n");
}else{
if(x>y) swap(x,y);
printf("%d %d\n",x,y);
}
}
return 0;
}