首页 > 代码库 > hdu 5974 A Simple Math Problem(数学题）

hdu 5974 A Simple Math Problem(数学题）

2024-08-19 20:58:57   224人阅读

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).
 
题意：给你两个数a，b如果能找到两个数x，y使得x+y=a而且x，y的最小公倍数为b。
 
由于题目给出数据组数下、较多有12w组所以遍历会超时，所以要想办法直接求值。
根据题意能得到两个公式：
（1）x+y=a；
（2）x*y=b*k；（k为x，y的最大公约数）
显然有一个k在这里不好求答案所以想办法把k除掉。
将（1）左右都除k得到
（3）x／k+y／k=a／k；
再将（2）左右都除k得到
（4）（x／k）*（y／k）=b／k；
由于k是x，y的最大公约数，所以x／k，与y／k互质。所以a／k，与b／k也是互质。
所以问题就简化到求
i+j=a／gcd（a，b），i*j=b／gcd（a，b）；
i和j的解。
 
#include <iostream>#include <cmath>using namespace std;int X , Y;int gcd(int a , int b) {    return b > 0 ? gcd(b , a % b) : a;}int cal(int a , int b , int c) {    if(a * a - 4 * b < 0)        return 0;    int gg = a * a - 4 * b;    int fff = sqrt(gg);    if(gg != fff * fff) {        Y = -1 , X = -1;        return 0;    }    X = (a + fff);    Y = (a - fff);    if(X % 2 == 0 && Y % 2 == 0) {        X /= 2;        Y /= 2;        return 1;    }    else {        X = -1;        Y = -1;        return 0;    }}int main(){    int a , b;    while(cin >> a >> b) {        int c = gcd(a , b);        X = -1 , Y = -1;        if(cal(a / c , b / c , c) && X != -1 && Y != -1) {            cout << min(X , Y) * c << ‘ ‘ << max(X , Y) * c << endl;        }        else {            cout << "No Solution" << endl;        }    }    return 0;}

hdu 5974 A Simple Math Problem(数学题）


联系
我们