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亞洲區(qū)大連站-重現(xiàn)賽（感謝大連海事大學(xué)） 題意：給你兩個(gè)數(shù)，a,b,問你能不能找到兩個(gè)數(shù),x,y,滿足x + y = a; x,y的最小公倍數(shù)為b. 解題思路:剛開始暴力枚舉其中一個(gè)，最后tle了，看了題解之后，才知道可以直接解出來，但是要知道幾個(gè)結(jié)論，如果，k1,k2互質(zhì)，那么k1*k2與k1 + k2也互質(zhì),然后就是如何判斷一個(gè)數(shù)為完全平方數(shù)，就是直接開方之后，取整，然后平方，看等不等于原來的那個(gè)數(shù)，
#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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
