HDU 5974 数学

A Simple Math Problem

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

Problem DescriptionGiven 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

题意：给你 x+y=a, lcm(x,y)=b 求 a，b

思路：

易得：x/gcd+y/gcd=a/gcd, x/gcd*y/gcd=b/gcd; 令i=x/gcd, j=y/gcd; 即i*gcd+j*gcd=a,i*j*gcd=b ==> gcd(a,b)=gcd(x,y);解个方程即可。

PS：刚开始用的枚举gcd的方法，复杂度1e7，但是一直WA？？？

代码：

 1 #include<bits/stdc++.h>
 2 //#include<regex>
 3 #define db double
 4 #include<vector>
 5 #define ll long long
 6 #define vec vector<ll>
 7 #define Mt  vector<vec>
 8 #define ci(x) scanf("%d",&x)
 9 #define cd(x) scanf("%lf",&x)
10 #define cl(x) scanf("%lld",&x)
11 #define pi(x) printf("%d
",x)
12 #define pd(x) printf("%f
",x)
13 #define pl(x) printf("%lld
",x)
14 #define MP make_pair
15 #define PB push_back
16 #define inf 0x3f3f3f3f3f3f3f3f
17 #define fr(i,a,b) for(int i=a;i<=b;i++)
18 const int N=1e3+5;
19 const int mod=1e9+7;
20 const int MOD=mod-1;
21 const db  eps=1e-18;
22 const db  PI=acos(-1.0);
23 using namespace std;
24 map<ll,int> mp;
25 int main(){
26 //freopen("data.in","r",stdin);
27 //freopen("data.out","w",stdout);
28     ll a,b;
29     for(int i=0;i<=20005;i++){
30         ll x=1ll*i*i;
31         mp[x]=i;
32     }
33     while(scanf("%lld%lld",&a,&b)==2){
34         bool ok=0;
35         ll i=__gcd(a,b);
36 //        for(ll i=1;i*i<=a;i++) {
37             if(a%i==0&&b%i==0){
38                 ll bb=b/i,aa=a/i,y=aa*aa-4*bb;
39                 if(y<0||!mp.count(y)||(aa+mp[y])%2==1){printf("No Solution
");continue;}
40                 ll ans1=(aa+mp[y])/2;
41                 ll ans2=(aa-mp[y])/2;
42                 ans1*=i,ans2*=i;
43                 ll cnt1=a-ans1,cnt2=a-ans2;
44                 if(cnt1*ans1/__gcd(cnt1,ans1)==b){
45                     printf("%lld %lld
",cnt1,ans1);
46                 }
47                 else if(cnt2*ans2/__gcd(cnt2,ans2)==b){
48                     printf("%lld %lld
",cnt2,ans2);
49                 }
50             }
51 //        }
52 
53     }
54     return 0;
55 }