A Simple Math PRoblem
Time Limit: 2000/1000 MS (java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1086 Accepted Submission(s): 356
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 2016ACM/ICPC亚洲区大连站-重现赛（感谢大连海事大学） 题意：给你两个数，a,b,问你能不能找到两个数,x,y,满足x + y = a; x,y的最小公倍数为b. 解题思路:刚开始暴力枚举其中一个，最后tle了，看了题解之后，才知道可以直接解出来，但是要知道几个结论，如果，k1,k2互质，那么k1*k2与k1 + k2也互质,然后就是如何判断一个数为完全平方数，就是直接开方之后，取整，然后平方，看等不等于原来的那个数，
#include<bits/stdc++.h>using namespace std;typedef long long ll;ll a,b;ll gcd(ll x,ll y){ return x == 0?y:gcd(y%x,x);}int main(){ while(~scanf("%I64d%I64d",&a,&b)) { ll flag = true; ll g = gcd(a,b); ll k1,k2; ll term1 = 4LL*g*b; ll term2 = a*a; ll term = term2 - term1; if(term < 0) { flag = false; } ll ans = sqrt(term); if(ans*ans == term) { if((a + ans)%(2*g) != 0||(a - ans)%(2*g) != 0||(a - ans) <= 0) { flag = false; } else { k1 = (a + ans)/2; k2 = (a - ans)/2; } } else flag = false; ll resu1 = min(k1,k2); ll resu2 = max(k1,k2); if(flag) printf("%I64d %I64d/n",resu1,resu2); else printf("No Solution/n"); } return 0;}新闻热点
疑难解答
